EECS 311: Dynamic Programming Resources |
HomeCourse InfoLinks Grades |
Lectures Newsgroup Homework Exams |

As many authors note, DP is an approach, not an algorithm. At a high level (so high as to be almost useless), dynamic programming (DP) can be viewed in two different ways:

- Taking a recursive top-down solution and caching (memoizing) the intermediate shared results for efficiency
- Solving a big problem by building a table of best solutions to simpler problems, incrementally, bottom-up.

The first view is helpful when you have a recursive but exponential solution, e.g., the standard recursive function for calculating Fibonacci numbers, and you want to create a more efficient solution.

Weiss discusses several examples of DP in Chapter 10, Section 10.3, but never actually defines what DP is.

Here are some readable online resources that describe DP solutions to various problems. I deliberately avoided the more mathematical sites:

- What is Dynamic Programming (PDF) by Sean R. Eddy -- a gentle introduction to DP for biologists, using the DNA alignment example.
- Dumitru's TopCoder tutorial on dynamic programming -- another brief introduction, using the example of making change
- The Wikipedia entry on Dynamic Programming -- introduces the important required property of optimal substructure
- Jesse's Introduction to Dynamic Programming -- similar to the Wikipedia entry; includes the maximal subsequence sum problem, which our textbook introduced in chapter 1 of Weiss
- Chapter 6 from Kleinberg and Tardos' Algorithm Design -- an excellent extended discussion. We use this book as a text sometimes. It's a better introduction to algorithmic analysis but weak on programming.
- Chapter 15 from Chinneck's Practical Optimization (PDF) -- notes that Dijsktra's cheapest path algorithm is DP, and gives a nice study of the equipment replacement problem and the classic knapsack problem
- Moshe Sniedovich's Dijkstra's Algorithm Revisited -- an extended look at Dijsktra's algorithm from a DP optimization point of view

Memoization is a classic programming technique, easy to implement in
some languages, like Lisp and Python, a little harder in strongly typed languages
like C++. Memoization is partularly relevant to dynamic programming, because
it's an alternative solution to the repeated subproblem problem (not a typo)
that comes up when `fn(n)` requires combining the values for
`fn(k)` where for some k < n. To avoid recalculating `fn(k)`
over and over:

- In DP you build a table of
`fn(k)`values bottom-up until you reach`fn(n)`. - In memoization, you write a recursive function that calculates
`fn(n)`top-down, using`fn(k)`, but you cache all intermediate values in some table, and check that table before doing any recursive call.

Some resources on this:

- C++ Hash Table Memoization: Simplifying Dynamic Programming by Mark Nelson, from Dr. Dobbs.
- the WikiBooks entry on Dynamic Programming begins with a discussion of memoization

To make it simpler to define a memoized recursive function, I created some templated classes, in memoize.h. These were designed to it pretty simple to convert normal recursive definitions of unary and binary functions to a memoized ones. For example, here's the classic recursive Fibonacci function:

long fib( int n ) { return ( n == 0 || n == 1 ) ? 1 : fib( n - 1 ) + fib( n - 2 ); }

Here's the same function, memoized. You call it the same way, e.g.,
`(fib 20)`

.

class Fib : public UnaryMemoFunction<int, long> { protected: long call( int n ) { return ( n == 0 || n == 1 ) ? 1 : memo( n - 1 ) + memo( n - 2 ); } } fib;

A subclass of `UnaryMemoFunction` must define `call()`
to do the actual calculations. Any recursive calls should call `memo()`
to cache the values returned.

The memoized function can be called just like the recursive function.
In addition, `fib.size()` will return how many calls have been stored
in the cache, and `fib.clear()` will empty the cache.

Here's an example of the binary recursive function for Pascal's Triangle (PDF):

long pascal( int r, int c ) { return ( r == 1 || c == 1 ) ? 1 : pascal( r, c - 1 ) + pascal( r - 1, c ); }

Here's the memoized version:

class Pascal : public BinaryMemoFunction<int, int, long> { protected: long call( int r, int c ) { return ( r == 1 || c == 1 ) ? 1 : memo( r, c - 1 ) + memo( r - 1, c ); } } pascal;

While a memoized function will not compete with optimized hand-coded
algorithms, there are still huge speedups possible with
intensively recursive functions like these. Here are the
timings on my desktop computer, using gcc 4.2, for `fib(40)`
and `pascal(20)`:

Fibonacci 40 = 165580141 2078 ticks (recursive) 0 ticks (memoized) Pascal's Triangle 16,16 = 155117520 2328 ticks (recursive) 0 ticks (memoized)

Finally, here's a classic dynamic programming problem: Longest Common Subsequence. An example test case:

std::string x = "ABDCBABC"; std::string y = "ADBCDBAB"; CHECK_EQUAL( "ABDBAB", lcs( x, y ) );

"ABDBAB" is one of several solutions. Can you find the others?

The recursive code for this is:

std::string lcs( std::string x, std::string y ) { if ( x.empty() || y.empty() ) { return ""; } else { char xc = lastChar( x ); char yc = lastChar( y ); return xc == yc ? lcs( prefix( x ), prefix( y ) ) + xc : longer( lcs( prefix(x ), y ), lcs( x, prefix( y ) ) ); } }

This uses some easily defined utility subfunctions for getting the last character in a string, the "prefix" of a string, which means all the characters except the last one, and the longer of two strings.

The memoized version is:

class LCS : public BinaryMemoFunction<std::string, std::string, std::string> { protected: std::string call( std::string x, std::string y ) { if ( x.empty() || y.empty() ) { return ""; } else { char xc = lastChar( x ); char yc = lastChar( y ); return xc == yc ? memo( prefix( x ), prefix( y ) ) + xc : longer( memo( prefix(x ), y ), memo( x, prefix( y ) ) ); } } } mlcs;

Running these two implementations on randomly generated DNA-like data yields the timings below. As can be seen, the problem becomes expensive very fast. There is also a very wide variation in running times for strings of the same length. This problem slows down so quickly that much more sophisticated algorithms are needed to handle the long strings that come up in real DNA.

*Comments? Send mail to
* c-riesbeck@northwestern.edu.