Dynamic programming via memoization

I personally find it much easier to make a recursive function efficient by caching previous solutions a.k.a a top down approach vs a bottom up approach.

There are so many interesting resources that go through some cool problems to which DP can be applied. The most interesting ones I found are the MIT 6.006 series on youtube by Erik Demaine. There, Erik discusses some nice basic properties of DP, such as it being equivalent to a DAG traversal etc, etc and then goes on to apply it to some pretty unconventional problems like playing the guitar or blackjack. Here’s the link : Video Lectures. They focus mainly on the bottom up approach.

Another compendium of  some classic DP problems is DP-Practice. Here again the flash animations mainly focus on the bottom-up approach.

In this blog post I’ll focus on some of the main techniques/ gotchas that I’ve found useful while using the top-down / memoization approach on recursive solutions.

 

  • If you are planning to apply memoization on your recursive function make sure that it returns a value ( the answer to the subproblem). Often recursive functions are void, with the state being stored internally, but it will take much more effort to convert such recursive functions to memoized DP’s
  • Make sure that your recursive problem is solving sub-problems and reducing the state-space for all the parameters. While writing recursive solutions, just because it is already very “brute-forcey”,  it is easy to forget that certain parts are unnecessary. Make sure to consistently prune the state at every call, and pass strictly the state that is required for that particular call. If you skip doing this, it will be impossible to memoize your DP solution.
  • Remember to pass in only the “independent” states and not the “dependent” state as parameters to your recursive function. For instance, let’s say you have a problem where you want to check if a string s1 is formed by some interleaving of strings s2 and s3. One possible state you could pass in the recursive function is the set{i, j, k} the indices for s1, s2 and s3 where you are currently positioned. However notice, that in this case, the variable i is not really required, it is dependent on j and k, basically i = j+k in any valid solution to the problem. Thus you really need to pass in just 2 variables  {j, k} in the state space.
  • Once you have decided the minimum set of parameters that make up your state space, the memoization is just about making either an array/ hashmap , that stores for each valid combination of the parameters, the solution that was computed by the function. Here’s why the previous step is important, the space complexity of your solution will grow as the number of parameters grow.
  • Now that you have a cache in place for storing solutions, you just need to modify your functions (at the logical level, there may of course be some other simple code changes you’ll need to make) so that :
    • on entering the function you check whether the particular combination of parameters already has a solution in the cache, if so simply return with the solution.
    • if not, then just continue the rest of the recursive function as before, but just before returning the result, make sure to store it in the cache, against the current set of parameter values.

And that should be it. This should usually be enough to quickly convert that cpu-hogging sloth of a recursive function to its much slicker DP cousin!

Of course a lot of caveats apply, and this is just the tip of the iceberg. Often top down approaches may still not be slick enough to pass the timing limits in some fancy competitive programming competition. But if you just want to be happy and satisfied about owning a toolkit to cook up some efficient solution to a DP problem, this is definitely not bad.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s