Today I’m going to be pausing the Mercurial content in favor of material I learned today in the algoganza study group here at the Recurse Center. This study group is working together to learn content that commonly comes up in job interviews and to prepare for the dreaded whiteboard technical interview. Today’s session focused on a new concept for me, dynamic programming, an approach one can use to solve problems that are conceptually amenable to a recursive approach, but where the naive recursive approach might be very slow.
To explore these ideas let’s think about the Fibonacci sequence. We can
calculate Fibonacci number $n$ with the formula $F_n = F_{n-1} +
F_{n-2}$. For $n=0$ and $n=1$ we impose $F_0 = 0$ and $F_1 = 1$. The
first few numbers in this sequence are $0, 1, 1, 2, 3, 5, 8, 13, \ldots$. This
formula is amenable to a recursive implementation because we can calculate new
numbers in the sequence using only information we collected about previous
numbers in the sequence.
We can write a recursive implementation of the $F_n$ function in Python like
this:
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)This works but is extremely slow:
In [2]: %time fib(5)
CPU times: user 20 µs, sys: 1 µs, total: 21 µs
Wall time: 29.1 µs
Out[2]: 5
In [3]: %time fib(10)
CPU times: user 153 µs, sys: 8 µs, total: 161 µs
Wall time: 98.9 µs
Out[3]: 55
In [4]: %time fib(15)
CPU times: user 0 ns, sys: 2.02 ms, total: 2.02 ms
Wall time: 1.33 ms
Out[4]: 610
In [5]: %time fib(20)
CPU times: user 2.81 ms, sys: 179 µs, total: 2.99 ms
Wall time: 2.48 ms
Out[5]: 6765
In [6]: %time fib(25)
CPU times: user 51.1 ms, sys: 0 ns, total: 51.1 ms
Wall time: 49.6 ms
Out[6]: 75025
In [7]: %time fib(30)
CPU times: user 204 ms, sys: 0 ns, total: 204 ms
Wall time: 202 ms
Out[7]: 832040
In [8]: %time fib(35)
CPU times: user 2.03 s, sys: 691 µs, total: 2.03 s
Wall time: 2.03 s
Out[8]: 9227465
In [9]: %time fib(40)
CPU times: user 22.9 s, sys: 3.65 ms, total: 22.9 s
Wall time: 22.9 s
Out[9]: 102334155
The problem is that we are calling the fib function far more times than we
actually need to. Rather than calculating, say, fib(15) only once, we instead
calculate it over and over again for all numbers greater than 15.
One way to improve this approach is to use memoization. That is, we cache the
output of our fib function the first time we call the function for a given
n. If we call the function again for the same n, we use the cached output
we saved and avoid recursively recomputing all Fibonacci numbers smaller than
n. The easiest way to implement memoization in Python is to use a decorator:
def memoize(f):
cache = {}
def wrapped(n):
if n not in cache:
cache[n] = f(n)
return cache[n]
return wrapped
@memoize
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)Here we’ve created a decorator memoize that stores a dictionary that caches
the results of the function, using the inputs to the function as the cache
keys. We then apply the memoize decorator to the fib function, which is
unchanged from above. This implementation is substantially faster, we’re now
able to calculate $F_{100}$ in less than a millisecond:
In [14]: %time fib(100)
CPU times: user 299 µs, sys: 0 ns, total: 299 µs
Wall time: 316 µs
Out[14]: 354224848179261915075
Memoization can be very useful if we don’t mind paying the memory cost of storing all inputs and outputs to all functions. All we need to do is create a cache and save results to the cache. The rest of the algorithm is completely unchanged and we still retain all the intuition we developed while thinking about the recursive approach.
There is a more optimal way to do this problem, using a dynamic programming
approach. To see why this might be the case, consider how the recursive and
memoized approaches we examined already are top-down approaches. We coded
things in a very general way such that our implementation doesn’t know ahead of
time how many times the fib function will get called or when it will
eventually get called with arguments that trigger the terminating conditions for
the recursion (e.g. n = 1 and n = 0). However, we know ahead of time that to
calculate the 40th Fibonacci number, we are definitely going to need the 0th
through 39th number. A more clever bottom-up algorithm takes advantage of this
knowledge. A dynamic Fibonacci solver looks like this:
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
nm1 = 0
nm2 = 1
for i in range(2, n+1):
fibi = nm1 + nm2
nm1 = nm2
nm2 = fibi
return fibiThis version uses constant memory and runs in $O(n)$ time. It also doesn’t use
the call stack to store temporary variables and is not susceptible to raising
errors due to running out stack frames (in Python) or overflowing the stack and
triggering undefined behavior (in an unsafe compiled language like C).
Let’s close this out with a discussion of one more problem that is amenable to this sort of approach. Here we’d like to know how many different ways we can make change for a dollar using US currency (that is, using pennies, nickles, dimes, quarters, half-dollars, and dollar coins). It may not be obvious that this problem is amenable to a recursive approach. One way to see this is to realize that one subset of solutions is the set of ways to make change for 99 cents along with one more penny. Another set is the set of ways to make change for 95 cents along with another nickel, 90 cents with a dime, and so on. All of these solutions depend on the solution of a smaller version of the problem - a classic signal that recursion might be useful. What about the other solutions? Well, we know that, for example, there is only one way to take a way to make change for 99 cents and make it a way to make change for a dollar: add another cent. So that means we’ve accounted for all of the ways to make a dollar with the set of coins that includes pennies. So the other set of solutions is the way to make change for a dollar using all coins but pennies. Again, we are dealing with a smaller problem, another recursive path.
Let’s take a look at Python code for this recursive algorithm:
def make_change(amount, denominations):
if len(denominations) == 0:
return 0
if amount == 0:
return 1
if amount < 0:
return 0
num_with_amount = make_change(amount - denominations[0], denominations)
num_without_denom = make_change(amount, denominations[1:])
return num_with_amount + num_without_denomThe terminating cases might look a little weird. The first, checking the number of denominations to consider, handles the case where we’re asked to make change with no coins at all. There’s no way to make change in this case, so the number of ways to make change from this branch of the recursive call graph is zero. The second case, when we’re asked to make change for 0 cents, corresponds to the case where we’ve made exact change already, so this branch contributes exactly one way to make change. Finally, if we’re asked to make change for a negative amount of currency that means that again this is an invalid way to make change for a dollar (the value of the coins goes over a dollar).
As with the Fibonacci numbers, this is a top-down approach. What would the bottom-up dynamic approach look like? One way to do it is to make use of a table that caches the results for simple cases and then builds up more complicated cases as we go:
import itertools
def make_change_dynamic(amount, denominations):
# Generate all combinations of the given denominations
# e.g. for a penny and a nickel, this would be just a penny, just a
# nickel, and a penny and a nickel
combinations = []
for l in range(1, len(denominations) + 1):
for x in itertools.combinations(denominations, l):
combinations.append(x)
# table to cache results
TABLE = {}
# terminating case for making change for 0 cents
for c in combinations:
TABLE[0, c] = 1
for i in range(1, amount + 1):
# terminating case for making change with no money
TABLE[i, ()] = 0
for c in combinations:
if i - c[0] < 0:
# terminating case for making change for negative cents
TABLE[i, c] = 0
elif i - c[0] == 0:
# exact change
TABLE[i, c] = 1
else:
TABLE[i, c] = TABLE[i - c[0], c] + TABLE[i, c[1:]]
return TABLE[amount, denominations]I suspect that there’s probably a fancier version that can compute the result with constant memory like the Fibonacci case we discussed above.
Another blog post diving into some more in-depth theory: https://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html
A set of dynamic programming practice problems: https://atcoder.jp/contests/dp/tasks