I was talking to a friend about dynamic programming and I realized his understanding of dynamic programming is basically converting a recursive function to an iterative function that calculates all the values up to the value that we are interested in. While this definition is not incorrect it only refers to a sub category of dynamic programs that is called the “bottom-up” solution to the dynamic programs.

Contrary to my friend’s belief, a dynamic programming solution can be recursive. However, in this approach you calculate previous values only when you need them, and only if you have not calculated these values already. This lazy solution of dynamic programs is called the “top-down” solutions. The top-down approach to dynamic programming is using a combination of recursive and memoization. In a generic recursive solution after you calculate the value of f(n-1) you probably throw it away. In the recursive solution, next time you need the f(n-1) value, you need to recalculate it.

The top-down dynamic programing approach is a combination of recursion and memoization. Memoization allows you to produce a look up table for f(x) values. As soon as you calculate f(n-1), you enter n-1 into a hash table (i.e., a Python dictionary) as the key and also enter f(n-1) as the value. This way, next time you need the f(n-1) you just look it up in your dictionary in O(1).

Let’s look at an example that I gave to my friend. Let’s solve the coins changing problem but just to make the code interesting we will solve a slightly harder problem. Here is the problem, assume you have pennies, nickels, dimes and quarters and you are interested in changing some arbitrary amount of money with these coins. We want to have a function named change() that is called like this ` change(100, [1,5,10,25])`

and returns a tuple like `(4, {25: 4})`

meaning that I need 4 coins and the dictionary will be how the coins are changed (all four are quarters).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# Coin changing problem def change(amount, coins): numberofcoins = 0 actualcoins = {} if len(coins) == 1: numberofcoins = amount / coins[0] actualcoins[coins[0]] = numberofcoins elif amount == 1: numberofcoins = 1 actualcoins[coins[0]] = 1 elif amount == 0: numberofcoins = 0 else: if (amount - coins[-1]>= 0): sol1 = change(amount-coins[-1], coins) sol2 = change(amount, coins[:-1]) numberofcoins += min(1+ sol1[0], sol2[0]) if 1+ sol1[0]<sol2[0]: if coins[-1] in actualcoins: actualcoins[coins[-1]] += 1 else: actualcoins[coins[-1]] = 1 actualcoins = { x: actualcoins.get(x, 0) + sol1[1].get(x, 0) for x in set(actualcoins) | set(sol1[1]) } else: actualcoins = actualcoins + min2[1] actualcoins = { x: actualcoins.get(x, 0) + sol2[1].get(x, 0) for x in set(actualcoins) | set(sol2[1]) } else: sol = change(amount, coins[:-1]) numberofcoins += sol[0] actualcoins = { x: actualcoins.get(x, 0) + sol[1].get(x, 0) for x in set(actualcoins) | set(sol[1]) } return (numberofcoins, actualcoins) coins = [1, 5, 10, 25] for i in range(1,104): print i, "-->", change(i, coins) |

Below is some sample outputs for this solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
1 --> (1, {1: 1}) 2 --> (2, {1: 2}) 3 --> (3, {1: 3}) 4 --> (4, {1: 4}) 5 --> (1, {5: 1}) 6 --> (2, {1: 1, 5: 1}) 7 --> (3, {1: 2, 5: 1}) 8 --> (4, {1: 3, 5: 1}) 9 --> (5, {1: 4, 5: 1}) 10 --> (1, {10: 1}) 11 --> (2, {1: 1, 10: 1}) 12 --> (3, {1: 2, 10: 1}) 13 --> (4, {1: 3, 10: 1}) 14 --> (5, {1: 4, 10: 1}) 15 --> (2, {10: 1, 5: 1}) 16 --> (3, {1: 1, 10: 1, 5: 1}) 17 --> (4, {1: 2, 10: 1, 5: 1}) 18 --> (5, {1: 3, 10: 1, 5: 1}) 19 --> (6, {1: 4, 10: 1, 5: 1}) 20 --> (2, {10: 2}) 21 --> (3, {1: 1, 10: 2}) ... ... ... 96 --> (6, {25: 3, 10: 2, 1: 1}) 97 --> (7, {25: 3, 10: 2, 1: 2}) 98 --> (8, {25: 3, 10: 2, 1: 3}) 99 --> (9, {25: 3, 10: 2, 1: 4}) 100 --> (4, {25: 4}) 101 --> (5, {25: 4, 1: 1}) 102 --> (6, {25: 4, 1: 2}) 103 --> (7, {25: 4, 1: 3}) |

While this solution works, this is painstakingly slow. This is because the code will calculate the value of change(9, [1,5,10,25]) every time you are calculating the change that is larger than 9 (or any other amount). When I timed 40,000 runs of this, it ended up spending 20 minutes calculating all the values. If you add memoization to this, it will take only 11 seconds.

Memoizing this function is slightly more difficult than a regular function that is like f(n). There, you can just have a hash table with n as key. But in our function we need to memoize values like change(9,[1,5,10]) and change(9,[1,5]) in different cells. There is a smart solution in Python cookbook for this problem. You can use Pickle module to convert both 9 and the [1,5,10] array to one single string and store the output of this input in a dictionary.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# # Coin changing problem import cPickle class memo: def __init__(self, fn): self.fn = fn self.memo = {} def __call__(self, *args): keystr = cPickle.dumps(args, 1) if keystr not in self.memo: self.memo[keystr] = self.fn(*args) return self.memo[keystr] @memo def change(amount, coins): numberofcoins = 0 actualcoins = {} if len(coins) == 1: numberofcoins = amount / coins[0] actualcoins[coins[0]] = numberofcoins elif amount == 1: numberofcoins = 1 actualcoins[coins[0]] = 1 elif amount == 0: numberofcoins = 0 else: if (amount - coins[-1]>= 0): sol1 = change(amount-coins[-1], coins) sol2 = change(amount, coins[:-1]) numberofcoins += min(1+ sol1[0], sol2[0]) if 1+ sol1[0]<sol2[0]: if coins[-1] in actualcoins: actualcoins[coins[-1]] += 1 else: actualcoins[coins[-1]] = 1 actualcoins = { x: actualcoins.get(x, 0) + sol1[1].get(x, 0) for x in set(actualcoins) | set(sol1[1]) } else: actualcoins = actualcoins + min2[1] actualcoins = { x: actualcoins.get(x, 0) + sol2[1].get(x, 0) for x in set(actualcoins) | set(sol2[1]) } else: sol = change(amount, coins[:-1]) numberofcoins += sol[0] actualcoins = { x: actualcoins.get(x, 0) + sol[1].get(x, 0) for x in set(actualcoins) | set(sol[1]) } return (numberofcoins, actualcoins) |

Running this code 40,000 times only takes 11 seconds as opposed to 20 minutes without memoization. I am however wondering if we can optimize the code even further?

I ran your code on my machine for 80000 times in 14.20s ish.

I was able to reduce it to 13.60s ish after using “in” instead of has_key in line 12.

“if str not in self.memo:”

It’s not a major performance improvement, but it’s definitely more Pythonic. Also, I don’t recommend using “str” as a variable name.

Then I ran the same code using cPickle and was able to run it in 3.42s ish.

You are right, cPickle was faster than pickle. On my machine it brought it down to about 8 seconds. Thanks for the suggestion.