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.
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.
