The memoization post ended on a promise : that caching a recursive function opens the door to a whole algorithmic technique called dynamic programming. Time to walk through that door. The name is intimidating and, as we will see, deliberately meaningless, but the idea behind it is one you already use when you climb stairs : to know how many ways there are to reach step $n$, you do not re-explore the whole staircase, you look at the two steps you just came from. Dynamic programming is that instinct made rigorous — and this post builds it from an exponential disaster, proves why it is allowed to work, fills two tables by hand, and shows exactly where it stops working.
1. The disaster we are trying to fix
Let us go back to the naive recursive Fibonacci of the memoization post and count precisely how bad it is. Let $T(n)$ be the number of calls made by fibo_recursive(n). The function returns immediately for $n<2$, and otherwise makes one call for $n-1$ and one for $n-2$ :
That recurrence looks like Fibonacci itself, and it is :
Proof. By strong induction. For $n=0$, $2F(1)-1 = 2\cdot 1 - 1 = 1 = T(0)$, and likewise for $n=1$. Assume the formula holds for $n-1$ and $n-2$. Then by $\eqref{eq:calls}$, $$ T(n) = 1 + \big(2F(n)-1\big) + \big(2F(n-1)-1\big) = 2\big(F(n) + F(n-1)\big) - 1 = 2F(n+1) - 1, $$ using the Fibonacci recurrence itself in the last step.
$\square$
Since $F(n) \sim \varphi^{n}/\sqrt{5}$ with $\varphi = \frac{1+\sqrt 5}{2} \approx 1.618$, the number of calls grows exponentially. For $n = 50$ that is $2F(51) - 1 \approx 4.1 \times 10^{10}$ calls, hours of computation, to produce a number that a schoolchild could reach in fifty additions.
In plain words : the recursion is not slow because recursion is slow. It is slow because it keeps forgetting. Figure 1 shows exactly what it forgets.
2. The key realisation : the tree is really a graph
Here is the whole idea of dynamic programming in one sentence. The recursion tree of Figure 1 is a lie. All those nodes labelled F2 are not different problems that happen to look alike, they are the same problem, drawn several times because a tree has no way of showing that two branches meet again.
Glue the identical nodes together and the tree collapses into a directed acyclic graph (DAG) of subproblems : one node per distinct question, one edge per dependency.
This reframing is the definition worth memorising :
In plain words : write down every distinct question you will ever need to answer, notice that they only depend on each other in one direction, then answer them in the right order and write each answer down. Two ingredients make it possible, and both must be present :
- Overlapping subproblems. The same question comes up many times. This is what makes remembering worthwhile — it is why Figure 1 collapses. Without it, storing answers is pure overhead.
- Optimal substructure. The optimal answer to a problem can be built from optimal answers to its subproblems. This is what makes remembering legal — and, unlike the first, it is a property you must actually prove.
There are two ways to walk the DAG, and they are the same algorithm seen from two ends :
- Top-down (memoization) : keep the recursion, add a dictionary. The call stack discovers the DAG lazily and, by returning from the deepest calls first, ends up visiting nodes in a valid topological order without you ever computing one.
- Bottom-up (tabulation) : throw the recursion away, work out the topological order yourself, and fill a table with a loop.
from functools import lru_cache
# top-down : keep the recursion, just add a memory
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
# bottom-up : the same DAG, walked in topological order
def fib_table(n):
F = [0, 1] + [0] * (n - 1)
for k in range(2, n + 1):
F[k] = F[k - 1] + F[k - 2]
return F[n]
Both are $\mathcal{O}(n)$ : each of the $n+1$ nodes is evaluated once, at constant cost. Top-down is easier to write and only ever touches the subproblems it actually needs ; bottom-up avoids the call stack and, as we will see in section 6, makes it obvious which rows of the table can be thrown away.
3. A real optimisation problem, where greed fails
Fibonacci is a counting problem. Dynamic programming earns its keep on optimisation problems, so let us take the smallest honest one.
Coin change. Given a set of coin denominations $S$ (unlimited supply of each) and a target amount $n$, pay exactly $n$ using as few coins as possible.
Take $S = \lbrace 1, 3, 4 \rbrace$ and $n = 6$. The obvious strategy is to be greedy : always grab the largest coin that still fits. That gives $4 + 1 + 1$, three coins. And it is wrong : $3 + 3$ pays the same amount with two. Greed fails because taking the $4$ is locally the best move and globally a mistake, and nothing in a greedy algorithm ever revisits that decision. 1
So we must consider every first move. Let $C(n)$ be the minimum number of coins for amount $n$. Whatever the optimal solution is, it contains at least one coin ; call it $c$. Remove it, and what remains pays $n - c$. That suggests
\[\begin{equation} C(0) = 0, \qquad C(n) = 1 + \min_{\substack{c \in S \\ c \le n}} C(n - c). \label{eq:coin} \end{equation}\]This is the step where beginners are told to “trust the recurrence”. Let us instead prove it, because the proof is the optimal-substructure property, and it is short.
Proof. We show the two inequalities.
($\le$) Let $c \in S$ with $c \le n$. Take any optimal payment of $n - c$, which uses $C(n-c)$ coins, and add one coin $c$ to it. The result is a valid payment of $n$ using $C(n-c) + 1$ coins. Since $C(n)$ is the minimum over all valid payments, $C(n) \le 1 + C(n-c)$. This holds for every admissible $c$, hence $C(n) \le 1 + \min_{c} C(n-c)$.
($\ge$) Take an optimal payment of $n$, using $C(n)$ coins. Because $n \ge 1$ it contains at least one coin ; pick one and call it $c_0$. Removing it leaves a valid payment of $n - c_0$ using $C(n) - 1$ coins. By minimality of $C(n - c_0)$ we get $C(n - c_0) \le C(n) - 1$, that is $C(n) \ge 1 + C(n - c_0) \ge 1 + \min_{c} C(n - c)$.
Both inequalities give equality.
$\square$
The second half is the classic cut-and-paste argument, and it is worth restating in its contrapositive form because that is how you will use it on new problems : if the remainder of an optimal solution were not itself optimal, we could cut it out, paste in a better sub-solution, and obtain a strictly better solution to the whole problem — contradicting the optimality we assumed. Every correct dynamic program rests on an argument of this shape.
Now the recurrence is licensed, we can fill the table $C(0), C(1), \dots, C(6)$ in order, each entry needing only entries already written.
The winner for $n = 6$ is the $3$-branch : $C(6) = 1 + C(3) = 1 + 1 = 2$, the two threes that greed could not find. The cost is now obvious : $\mathcal{O}(n \cdot \lvert S \rvert)$ time and $\mathcal{O}(n)$ space, against the $\mathcal{O}(\lvert S \rvert^{\,n})$ of the naive recursion.
4. Recovering the solution, not just its value
The table gives us the number $2$, not the coins. This is a general and often-forgotten point : a dynamic program computes an optimal value, and getting an optimal solution requires remembering, for each state, which choice achieved the minimum. Then you walk those choices backwards from the final state.
def min_coins(coins, amount):
INF = float("inf")
C = [0] + [INF] * amount
choice = [None] * (amount + 1) # coin achieving the min
for n in range(1, amount + 1):
for c in coins:
if c <= n and C[n - c] + 1 < C[n]:
C[n], choice[n] = C[n - c] + 1, c
if C[amount] == INF:
return None # amount cannot be paid
bag, n = [], amount
while n: # walk the choices back
bag.append(choice[n])
n -= choice[n]
return C[amount], bag
min_coins([1, 3, 4], 6) # (2, [3, 3])
The choice array costs one extra number per state and turns an answer into an explanation.
5. Two dimensions : the knapsack
Not every state is a single integer. Take the other canonical example.
0/1 knapsack. Given $m$ items, item $i$ having weight $w_i$ and value $v_i$, and a bag of capacity $W$, choose a subset of maximum total value whose total weight is at most $W$. Each item may be taken at most once.
The “at most once” is what forces a second dimension. If the state were only the remaining capacity, nothing would stop us from taking the same item twice. So the state must record how far down the item list we are as well : let $K(i, c)$ be the best value obtainable using only the first $i$ items with capacity $c$. Facing item $i$ we have exactly two options, and by the same cut-and-paste argument the best overall is the better of the two :
\[\begin{equation} K(i, c) = \max \underbrace{\big\{\, K(i-1,\, c)}_{\text{leave item } i}, \; \underbrace{K(i-1,\, c - w_i) + v_i \,\big\}}_{\text{take it, if } w_i \le c}, \qquad K(0, c) = 0. \label{eq:knap} \end{equation}\]In plain words : go through the items one at a time and, for every possible remaining capacity, ask “am I better off skipping this item, or taking it and having less room for the rest ?” The DAG is now a grid : each cell depends on one cell directly above it and one cell above and to the left.
Read the bottom-right corner : the best value is $\mathbf{9}$. Note which items achieve it. Following the choices backwards, $K(4,7) = K(3,7)$ so item $(5,7)$ was left out despite being the most valuable single item ; then $K(3,7) \ne K(2,7)$ so item $(4,5)$ is in, dropping us to $K(2,3)$ ; then $K(2,3) \ne K(1,3)$ so item $(3,4)$ is in too. The optimum is ${(3,4), (4,5)}$, weight $7$, value $9$ — again a solution no greedy rule based on value, weight, or value-per-weight would produce.
# items = [(weight, value), ...]
def knapsack(items, W):
K = [[0] * (W + 1) for _ in range(len(items) + 1)]
for i, (w, v) in enumerate(items, start=1):
for c in range(W + 1):
K[i][c] = K[i - 1][c] # leave it
if w <= c: # or take it
K[i][c] = max(K[i][c],
K[i - 1][c - w] + v)
return K[len(items)][W]
knapsack([(1, 1), (3, 4), (4, 5), (5, 7)], 7) # 9
6. Saving space : the rolling table
Look again at $\eqref{eq:knap}$ : row $i$ reads only row $i-1$. Rows $0$ to $i-2$ are dead weight. So we can keep a single array and overwrite it in place, provided we sweep the capacities downwards so that K[c - w] still holds the previous row’s value when we read it :
def knapsack_1d(items, W):
K = [0] * (W + 1)
for w, v in items:
# downwards, so K[c - w] still holds row i-1
for c in range(W, w - 1, -1):
K[c] = max(K[c], K[c - w] + v)
return K[W]
Memory drops from $\mathcal{O}(mW)$ to $\mathcal{O}(W)$, a change that routinely decides whether a dynamic program fits in RAM. The price is that we can no longer backtrack through the table to recover which items were chosen — the same memoization trade-off between speed, memory and information, one level up.
7. The recipe
Every dynamic program you will ever write is these five steps, in this order.
- Name the state. What is the smallest set of facts that fully describes a subproblem ? ($n$ for coin change ; the pair $(i, c)$ for the knapsack.) Get this wrong and nothing else works.
- Write the recurrence. Consider all the possible first (or last) decisions and express the answer in terms of smaller states.
- Prove optimal substructure. Cut and paste : assume a sub-solution is not optimal, replace it with a better one, contradict the optimality of the whole.
- Order the states. Find a topological order of the dependency DAG — often just “increasing $n$” or “row by row”. Or skip it entirely by memoizing the recursion top-down.
- Reconstruct the answer, if you need the solution and not only its value, by storing the argmin/argmax at each state.
The complexity then reads straight off the table : (number of states) $\times$ (cost of one transition).
8. Where it breaks, and why that is interesting
Dynamic programming is not universal, and knowing its boundary is what turns it from a trick into a tool.
Without optimal substructure, it is simply wrong. The textbook counterexample (Cormen et al., 2009) is the longest simple path between two vertices of a graph. Shortest paths decompose beautifully — a sub-path of a shortest path is a shortest path — which is why Dijkstra and Bellman–Ford work. Longest simple paths do not : the sub-paths of an optimal long path need not be optimal, because “simple” (no repeated vertex) is a global constraint that two independently-optimal halves can violate when you glue them together. The problem is NP-hard, and no amount of tabulation will save it.
The table can be exponentially large. The knapsack runs in $\mathcal{O}(mW)$, which looks polynomial. It is not : the input writes $W$ in about $\log_2 W$ bits, so the table size $W$ is exponential in the size of the input. This is called pseudo-polynomial, and it is exactly why the knapsack remains NP-hard even though we just solved it in a dozen lines. The same effect kills exact dynamic programming for the travelling salesman, whose state must record the set of already-visited cities : the Held–Karp algorithm (Held & Karp, 1962) is $\mathcal{O}(2^{m} m^{2})$, a spectacular improvement on the $\mathcal{O}(m!)$ of brute force, and still hopeless past a few dozen cities. Bellman named this state explosion the curse of dimensionality (Bellman, 1957).
And it is stubbornly sequential. Each cell waits for its predecessors, which is the exact opposite of the independent-chunks structure that MapReduce needs to scale. Dynamic programs parallelise only along the anti-diagonals of the table, where cells happen to be mutually independent — never along the direction of the recurrence.
9. It is everywhere, once you see the DAG
The pattern generalises far beyond puzzles. Sequence alignment and edit distance fill a two-dimensional grid exactly like the knapsack, and are the backbone of diff and of DNA comparison. Viterbi decoding finds the most likely hidden state sequence by tabulating over (time $\times$ state). The deletion–contraction recurrence used to compute chromatic polynomials generates the same graph over and over, and is a textbook candidate for memoization on isomorphism classes.
And one you have already met : backpropagation. The computational graph of a neural network is the DAG, the upstream gradient at each node is the memoized subproblem value, and the backward pass is the topological sweep. It computes every partial derivative in a single pass for the same reason our table did — because it refuses to answer the same question twice.
10. Conclusion
Dynamic programming is not a family of tricks to memorise, it is one observation applied with discipline : a recursion whose calls overlap is secretly a DAG, and a DAG should be evaluated once, in order. Memoization is that observation applied lazily from the top ; tabulation is the same observation applied deliberately from the bottom. The exponential blow-up of Figure 1 and the polynomial table of Figure 2 describe the same computation — the only difference is whether the algorithm bothers to remember.
What makes it an engineering discipline rather than a reflex is the middle step, the one this post insisted on : proving that the pieces of an optimal solution are themselves optimal. When that cut-and-paste argument goes through, you get an algorithm and a proof at the same time. When it does not — longest simple path — no table in the world will rescue you, and that failure is itself worth knowing.
References
- Bellman, R. (1954). The Theory of Dynamic Programming. Bulletin of the American Mathematical Society, 60(6), 503–515.
@article{Bellman1954, author = {Bellman, Richard}, title = {The Theory of Dynamic Programming}, journal = {Bulletin of the American Mathematical Society}, volume = {60}, number = {6}, pages = {503--515}, year = {1954} } - Bellman, R. (1957). Dynamic Programming. Princeton University Press.
@book{Bellman1957, author = {Bellman, Richard}, title = {Dynamic Programming}, year = {1957}, publisher = {Princeton University Press} } - Bellman, R. (1984). Eye of the Hurricane: An Autobiography. World Scientific.
@book{Bellman1984, author = {Bellman, Richard}, title = {Eye of the Hurricane: An Autobiography}, year = {1984}, publisher = {World Scientific} } - Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
@book{Cormen2009, author = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford}, title = {Introduction to Algorithms}, edition = {3rd}, year = {2009}, publisher = {MIT Press} } - Held, M., & Karp, R. M. (1962). A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196–210.
@article{HeldKarp1962, author = {Held, Michael and Karp, Richard M.}, title = {A Dynamic Programming Approach to Sequencing Problems}, journal = {Journal of the Society for Industrial and Applied Mathematics}, volume = {10}, number = {1}, pages = {196--210}, year = {1962} }
-
The number of coins is not the only sensible objective, and the greedy algorithm is not always wrong : for the “canonical” systems used by real currencies (such as $\lbrace 1,2,5,10,20,50 \rbrace$) greed provably matches the optimum. Deciding whether a given coin system is canonical is itself a non-trivial problem — which is a good reason to reach for $\eqref{eq:coin}$ and stop worrying. ↩