# C++ Hash Table Memoization: Simplifying Dynamic Programming

Dynamic Programming (DP) is a useful technique for algorithm development that is saddled with an unfortunate name. When we refer to greedy algorithms, or the use of divide-and-conquer techniques, the name provides excellent semantic clues as to what is going on. With dynamic programming, no such luck, but I'm afraid were stuck with name for historical reasons.

## More Insights

More >>

More >>

### Webcasts

More >>

Dynamic programming is frequently used to solve optimization problems -- that is, problems where a number of choices can be made to lead to some maximum or minimum value. Optimization problems can often be solved efficiently using straightforward iterative or divide and conquer techniques, but dynamic programming becomes useful when those other techniques lead to overlapping subproblems.

This Wikipedia article on dynamic programming gives a good example of what is meant by overlapping subproblems. Imagine that you are a C programmer who decides to use a recursive function call to calculate the nth Fibonacci number:

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

This code is correct, but it leads to a lot of extra work. Figure 1 shows a map of the recursive calls made using this algorithm:

Figure 1: The Call Map for fib(6)

For example, `fib(4)` is called twice, which leads to a large duplicated tree of recursive calls. All in all, a huge amount of wasted effort.

Dynamic programming provides a good way to avoid duplicate work done solving overlapping subproblems, but for the results to be useful, the problem has to adhere to the optimal substructure property.

Saying that a problem has this property is just a way of saying that we can find an optimal solution for problem A by breaking it down into problems B and C, both of which are optimal as well. Chapter 15 of Introduction to Algorithms gives nice examples of cases where this property holds, and where it doesn't.

### Defeating Overlapping Subproblems

Dynamic programming aims to defeat this problem of repeatedly solving overlapping subproblems. Conventionally, this is done by converting the algorithm to one that uses a bottoms up approach, combined with some global storage for intermediate results.

As an example, we could solve the Fibonacci problem using a bottoms-up approach with C++ code that looks something like this:

```int fib(int n)
{
std::vector results( n );
results[ 0 ] = results[ 1 ] = 1;
for ( int i = 2 ; i <n ; i++ )
results[ i ] = results[ i - 1 ] + results[ i - 2 ];
return results[ n - 1 ] + results[ n - 2 ];
}
```

In this case we only calculate the value of each `fib(n)` once, completely eliminating the duplicate calculation of those duplicate subproblems.

Most examples of DP that you find in textbooks or on the web will use a table or array to hold the intermediate results from problems. Examples of algorithms that use this type of memoization include Sequence Alignment, Matrix Chain Multiplication, and Optimal Binary Search Trees.

Using the tabular approach for storing subproblems often works well with a bottoms up implementation of the algorithm. DP algorithms typically start by solving the smallest subproblems, storing the results, combining some of those, storing the results in a new level of the table, and so on, until the top case is reached. Again, most of the tutorial DP examples you see will combine a bottoms-up approach with tabular subproblem storage.

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>