Channels ▼
RSS

C/C++

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

White Papers

More >>

Reports

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.


Related Reading






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

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

Video