The class of Dynamic Programming problems are very interesting. These problems all boil down to a class of optimization problems. Such problems are characterized by the distinctive reduction in their design. This reduction can lead to smaller sub-problems that are solved and the results bubbled up. In essence, dynamic programming problems are solved bottom-up, since the results of the sub-problems drive those above them.

The problem with such a technique lies in the fact that every solution requires you to solve every sub-problem to obtain an optimal solution. Memoization provides a simple and largely effective solution to alleviate this problem by storing results to these overlapping sub-problems for future use. Let’s look at an example using the evergreen fibonacci series:

**Inside the guts of Memoization**

The naive solution to recursive fibonacci series is :

int fib (int n) { if( n <=1 ) return 1; else return fib ( n-1 ) + fib ( n-2 ); }

Let’s look at what happens when we run it for a couple of values :

fib (5) ; // = fib(4) + fib(3) // = (fib(3) + fib(2)) + (fib(2) + fib(1)) // = ( (fib(2) + fib(1)) + (fib(1) + fib(0)) ) + // ( (fib(1) + fib(0)) + fib(1)) // = ( ( (fib(1) + fib(0)) + fib(1)) + // (fib(1) + fib(0)) ) + ( (fib(1) + fib(0)) + fib(1)) // 7 '+' operators. fib (6) ; // 6 overlapping subproblems, // results in '+' operator being run 11 times, // extrapolating from above.

But we already calculated fib (5), didn’t we? And since

fib (6) = fib (5) + fib(4);

and

fib (5) = fib(4) + fib(3);

We’ve already calculated fib (4) too. So fib (6) needs to just add the 2 values, resulting in just a single ‘+’ operation.

To use this information in our solution, let’s use a global map that stores intermediate solutions. (we can use hash_maps for faster un-ordered access when the TR1 specification and C++0x is standardized)

std::map<int, int> fibHash; int memoized_fib (int n) { std::map<int, int>::iterator fibIter = fibHash.find(n); if( fibIter != fibHash.end() ) return *fibIter; int fib_val; if( n <=1 ) fib_val = 1; else fib_val = memoized_fib ( n-1 ) + memoized_fib ( n-2 ); fibHash[ n ] = fib_val; return fib_val; }

This is a fairly one off solution, and requires modifications for using with multiple functions… but with C++0x we can do fully automatic memoization as described here : http://cpptruths.blogspot.in/2012/01/general-purpose-automatic-memoization.html

**Coming up** : my feeble attempt at auto-memoization in the current version of C++.