Data Structures and Algorithms

Dynamic Programming

Printable Version

To implement a dynamic programming solution to a problem, start out by writing a simple recursive implementation. Once completed and debugged, apply the following steps to convert the function:

(1) count how many formal parameters are changing in the recursive call - this is the dimensionality of your table

(2) look at the range of the values sent to the recursive function - these ranges are the sizes of your table

(3) build a table of the correct dimensionality and size

(4) convert the recursion to table operations

(5) fill out the table in the direction indicated by the recursive calls

(6) move the base cases

(7) retrieve the desired output from the table

function fib(n) { if (n == 0) return 0; else if (n == 1) return 1; else return fib(n-1) + fib(n-2); }

return fib(n-1) + fib(n-2);becomes:

t[i] = getTable(i-1) + getTable(i-2);Note (and this is important) that the changing from

function getTable(i) { return t[i]; }

We start our loop at the smallest value of

for (i = 0; i <= n; ++i) //note that n is included ???The recursive calls that were converted to table operations now become the body of the loop:

for (i = 0; i <= n; ++i) t[i] = getTable([i-1) + getTable(i-2);

function getTable(i) { if (i == 0) return 0; else if (i == 1) return 1; else return t[i]; }

return t[n];

function fib(n) { var t = makeTable(n+1); for (var i = 0; i <= n; ++i) t[i] = getTable(n-1) + getTable(n-2); return t[n]; }While the original

- one dime and one penny
- two nickels and one penny
- one nickel and six pennies
- eleven pennies

function makeChange(amount,index,coins) { if (amount == 0) return 1; //this is a legal solution if (amount < 0) return 0; //not a legal solution if (index == coins.size) return 0; //not a legal solution //find the number of combinations using the current coin var with = makeChange(amount-coins[index],index,coins); //find the number of combinations without using the current coin var without = makeChange(amount,index+1,coins); return with + without }Like

t = makeTable(amount+1,coins.size);

with = makeChange(amount-coins[index],index) without = makeChange(amount,index+1) return with + without;as this:

with = getTable(a-coins[i],i); without = getTable(a,i+1); t[a][i] = with + without;

We start our outer loop at the smallest value larger than the base cases. We end the loop after we reach the maximum value, which is

for (a = 1; a <= amount; ++a) ???We start the inner loop at the largest legal index and end it at the smallest legal index:

for (a = 1; a <= amount; ++a) for (i = coins.size-1; i >= 0; --i) ???As with

for (a = 1; a <= amount; ++a) for (i = coins.size-1; i >= 0; --i) { with = getTable(a-coins[i],i); without = getTable(amount,i+1); t[a][i] = with + without; }

function getTable(a,i) { if (a == 0) return 1; //this is a legal solution if (a < 0) return 0; //not a legal solution if (i == coins.size) return 0; //not a legal solution return t[a][i]; }Note that we are referencing the coins array in the third base case, so we need to pass the coins array to

function getTable(a,i,coins) { if (a == 0) return 1; //this is a legal solution if (a < 0) return 0; //not a legal solution if (i == coins.size) return 0; //not a legal solution return t[a][i]; }We also need to update the calls to

return t[amount][index];

function makeChange(amount,index,coins) { var a,i; //build the table var t = makeTable(amount+1,coins.size); //fill out the table for (a = 1; a <= amount; ++a) for (i = coins.size-1; i >= 0; --i) { with = getTable(a-coins[i],i,coins); without = getTable(amount,i+1,coins); t[a][i] = with + without; } //return the desired result return t[amount][index]; }The original

function mm(rows,cols,lo, hi) { var i; if (lo == hi-1) return 0; var best = INFINITY; for (i = lo+1; i < hi; ++i) //try all split points { var left = mm(rows,cols,lo,i); var right = mm(rows,cols,i,hi); //calculate muls for left-side matrix times right-side matrix var last = rows[lo]*cols[i-1]*cols[hi-1]; var total = left + right + last; if (total < best) best = total; } return best; }Because of the interleaved looping and recursion, turning this recursive solution into a dynamic programming solution is a bit involved. A more straightforward approach is

function mm2(rows,cols,lo,hi,table) { var i; if (lo == hi-1) return 0; if (table[lo][hi] != EMPTY) return table[lo][hi]; //memoized! var best = INFINITY; for (i = lo+1; i < hi; ++i) { var left = mm2(rows,cols,lo,i,table); var right = mm2(rows,cols,i,hi,table); var last = rows[lo]*cols[i-1]*cols[hi-1]; var muls = left + right + last; if (muls < best) best = muls; } table[lo][hi] = best; //take a memo return best; }The table that is passed into the memoized version of the function is constructed in the same way as in dynamic programming: the dimensionality is the number of changing formal parameters and the extent of a dimension is the range of values for the corresponding formal.

While the non-memoized solution takes exponential time, the memoized solution takes quadratic time. Since memoization is so simple to implement, it has supplanted dynamic programming as the