Lecture VII · Data Structures & Algorithms
Dynamic programming
Last time we watched naive Fibonacci detonate: a two-line function whose call tree
doubles at every level, so fib(35) sits there grinding while fib(35) computed a
smarter way returns before you blink. That explosion was not a quirk of recursion. It
was a signal, and dynamic programming is what we do once we learn to read it.
The same climb, four ways
Dynamic programming sounds like a technique. It is closer to a habit of mind: notice when a problem solves the same smaller problem over and over, and arrange to solve each one once. To see what that buys us, it helps to line up four ways of attacking the same job and watch them pull apart. Fibonacci is the cleanest specimen, so it will be our spine all lecture, but the four attitudes travel everywhere.
The first is greedy: at each step grab whatever looks best right now and never look back. Fast, simple, and correct only for a lucky class of problems. The second is plain recursion: state the answer in terms of smaller answers and let the call stack do the bookkeeping. Honest, but as we saw, sometimes catastrophically wasteful. The third is memoization, or top-down dynamic programming: the same recursion, but with a notebook where you jot down each answer the first time you compute it and read it back thereafter. The fourth is tabulation, or bottom-up dynamic programming: throw the recursion out entirely, order the subproblems from smallest to largest, and fill a table so that every answer you need is already sitting there when you reach for it. Memoization and tabulation are the two faces of dynamic programming, and by the end they will feel like the same idea told forwards and backwards.
Recursion, and the waste it hides
Recall the definition that started the trouble:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
It is a perfect transcription of the mathematics, and that is exactly why it is slow. Ask
for fib(6) and it asks for fib(5) and fib(4). But fib(5) also asks for fib(4),
so now fib(4) gets computed twice, from scratch, subtree and all. Go one level deeper and
fib(3) shows up three times, fib(2) five times. The tree is not doing new work at each
node; it is redoing the same handful of subproblems again and again, and the number of
redundant recomputations is what grows like .
That is the diagnosis, and it has a name: overlapping subproblems. The recursion keeps bumping into the same smaller instances, and because it has no memory, each collision costs it a fresh subtree. Draw the tree and the waste is not subtle, it is most of the picture. The plate below draws it for you and, more to the point, lets you turn the waste off.
Memoization: remember what you already solved
The fix is almost insultingly small. Keep a dictionary. Before computing fib(n), look to
see whether you already have it; if so, hand it back; if not, compute it once and write it
down before you return.
def fib(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
Nothing about the shape of the recursion changed. We still say fib(n - 1) + fib(n - 2).
All we added is the cache, and the cache changes everything, because the second time a
subproblem is requested it is now a one-line lookup instead of an entire subtree. The first
time we need fib(4) we pay for its whole subtree; every time after, fib(4) is a single
read. The exponential tree collapses inward and what is left is linear: each of fib(2)
through fib(n) computed exactly once, and a scattering of cache hits at the pruned
branches.
| n | fib(n) | naive · O(2ⁿ) | memoized · O(n) |
|---|---|---|---|
| 4 | 3 | 9 | 7 |
| 5 | 5 | 15 | 9 |
| 6 | 8 | 25 | 11 |
| 7 | 13 | 41 | 13 |
| 8 | 21 | 67 | 15 |
Every naive call re-expands subproblems it has already solved; the memo solves each of fib(2)…fib(n) once and reads the rest from a cache.
Notice one honest detail the plate is careful about. The base cases fib(0) and fib(1)
return directly and never enter the memo, so both little leaves still appear even in the
memoized tree; only the genuinely expensive values, fib(2) and up, turn into cache hits.
That is why the memoized count lands on exactly rather than something even smaller.
The lesson survives the fine print: caching turns a tree into something that barely
branches.
The harness counts calls directly, the way this course always prefers: no clock, just a
tally of how often fib runs. Watch the two columns diverge as n climbs. The naive column
roughly doubles each row; the memoized column crawls up by twos.
Tabulation: build the table from the bottom
Memoization is top-down: it starts at the answer you want and recurses down, filling the
cache lazily as questions come up. Tabulation flips the arrow. If we know we will need
every one of fib(0) through fib(n) anyway, why wait to be asked? Order them smallest to
largest and fill a table straight through, so each entry is ready before anything reaches
for it.
def fib_table(n):
if n <= 1:
return n
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
No recursion, no call stack, no cache-miss checks: just a loop that walks up the table once. It does the same linear amount of work as the memoized version, but with a flat loop instead of n deep stack frames, which matters the moment n gets large enough that recursion would overflow the stack. This is the everyday shape of a bottom-up dynamic program: an array indexed by subproblem, a base case or two written in by hand, and a recurrence that fills each cell from cells already filled.
Once the table is bottom-up, a second economy appears. To compute table[i] we only ever
look back two cells. So we do not need the whole array; two variables suffice, and the space
drops from to .
def fib_fast(n):
prev, curr = 0, 1
for _ in range(n):
prev, curr = curr, prev + curr
return prev
That is the whole arc in one function: the naive exponential recursion, tamed to linear time by remembering, and now trimmed to constant space by noticing how little of the table we actually keep alive. Not every dynamic program collapses this far, but the move, “which of the filled cells do I still need?”, is always worth asking.
The Union steps
Fibonacci is a fine specimen and a terrible motivation, because nobody outside a mathematics department urgently needs the thirty-fifth Fibonacci number. So let me put the same recurrence somewhere you have stood.
Outside the Student Union there is a wide, shallow flight of steps facing Fairfield Way, the kind people sit on with a coffee between classes because they are more bleacher than staircase. Watch anyone climb them and you will see two strides: one step at a time, or two at a time when they are late. Here is the question. How many distinct ways are there to get to the top?
Do not reach for a formula. Reach for the last stride, which is the move that solves almost every counting problem of this shape. Whatever route somebody took, the final stride landed them on the top step either from one step below or from two steps below. Those two cases are mutually exclusive, and together they cover everything, so the routes to step are exactly the routes to step plus the routes to step :
That is Fibonacci, shifted by one, arrived at from a staircase rather than from rabbits. And now the four attitudes from the start of the hour are not abstractions, they are four ways to count the same steps. Recurse naively and you re-count the routes to step 7 over and over, once for every path down to it. Memoize and you are a person with a notebook, standing at the top, asking “how many routes to step 11?” and writing each answer down the first time somebody works it out. Tabulate and you are a person standing at the bottom, walking up, writing the count on every step in order, and never having to ask anybody anything, because by the time you arrive at a step the two numbers you need are already chalked on the two steps below you.
The bench below counts a twelve-step flight both ways and, more usefully, prints the order in which the memo was actually filled. That order is the thing to stare at.
Read that last line carefully. The memo was asked about step 12 first, but it was written 2, 3, 4, and on up to 12. The recursion had to descend all the way to the base cases before it could write anything down, and then it filled the notebook from the bottom up on the way back. Which is precisely what the table does directly, without the descent. That is what I meant by the two faces of one idea: memoization is tabulation discovered lazily, in the order the questions happen to arrive, and tabulation is memoization with the order worked out in advance.
Memo or table: the space you keep
If they compute the same cells in the same order, is there ever a reason to prefer one? Yes, and the reason is usually space, so it is worth being precise about who pays for what.
A table pays for the whole index range, cells, whether or not you ever look at them. A memo pays only for the subproblems the recursion actually reaches. When every subproblem is reachable, as on the one-or-two staircase, those are the same bill and the table wins on constants: an array is cheaper per cell than a dictionary, with no hashing and no cache misses chasing buckets around memory.
But now suppose the strides are not 1 and 2. Suppose you can only move in strides of 10 or 25, which is a strange staircase but a completely ordinary shape for a real problem (it is the coin problem in disguise, and we are about to meet it properly). Now most step numbers are simply unreachable. The table dutifully allocates and fills all hundred and one of them anyway; the memo touches a couple of dozen and never learns that the others exist. When the reachable set is sparse, top-down memoization is not just a stylistic preference, it is asymptotically less memory.
So the ledger has three entries, and you should be able to recite them. Tabulation costs the whole index range but runs as a flat loop with no stack and the smallest possible constants. Memoization costs only the reachable subproblems but carries a dictionary and a call stack deep enough to worry about. And when the recurrence looks back only a fixed distance, as Fibonacci looks back two, neither one is necessary: keep a rolling window of that many variables and the space drops to . Ask which of the three you are entitled to before you write a line of it.
When greedy is enough, and when it lies
We skipped greedy, and it deserves a fair hearing, because sometimes it is exactly right and much cheaper than a full table. Making change is the classic stage for the argument. To make 63 cents with US coins, take the biggest coin that fits and repeat: a quarter, another quarter, a dime, three pennies. Greedy, and optimal. For the US system it always is, and you would be foolish to build a table when grabbing the largest coin each time provably wins.
The trouble is that greedy’s correctness depends on the coins, not just on the strategy. Give it the denominations 1, 3, and 4 and ask for 6. Greedy grabs a 4, then can only add 1 and 1, for three coins. But 3 + 3 is two coins. Greedy walked confidently off a cliff, because the locally best first move ruled out the globally best answer. When you cannot prove your greedy choice never forecloses a better future, you fall back to dynamic programming, which considers every subproblem instead of betting on one.
def min_coins(coins, amount):
# best[a] = fewest coins that make a; +1 sentinel means "unreachable".
best = [0] + [amount + 1] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
best[a] = min(best[a], best[a - c] + 1)
return best[amount] if best[amount] <= amount else -1
This is tabulation again, on a less obvious table. Each best[a] is built only from smaller
entries best[a - c] that are already final, and by considering every coin at every amount
it never gets seduced by a first move that looks good and ends badly. Slower than greedy, and
correct for any coin system you hand it. That is the trade dynamic programming always offers:
more work, in exchange for not having to be lucky.
Reconstructing the answer, not just its value
Look again at what min_coins returns. A number. It tells you that 6 cents takes two coins,
and then it shrugs. In almost every application that is the less interesting half of the
answer: a cash register needs to know which coins, a route planner needs the road names,
a diff tool needs the edits. The table knows. It just was not asked to say.
The fix is a habit worth acquiring early, because it generalises to every dynamic program you will ever write. Alongside the table of values, keep a second array recording why each cell got the value it did: which choice was the one that won. Then, when the table is full, start at the answer cell and walk the choices backwards until you arrive at a base case. The sequence you walk through is the solution itself.
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
choice[a] = c # remember WHY this cell got its value
One extra array, one extra assignment inside the loop that was already running, and no change at all to the asymptotics: reconstruction costs on top of a table you had already paid for, because the walk backwards takes one step per coin in the answer. That is the general shape. Fill forwards recording decisions; walk backwards reading them off.
Two moving parts: longest common subsequence
Everything so far has had a one-dimensional table, indexed by a single number: the step, the
amount. That makes dynamic programming look like a trick for staircases. So here is the
problem that breaks the habit, and it is the one you are most likely to meet in the wild,
because it is what git diff is doing.
A subsequence of a string is what is left after you delete some characters without
reordering the rest. SORR is a subsequence of STORRS, and it is also a subsequence of
SORROW, so it is a common subsequence of the two. The question is how long the longest
one is.
Now do the same move that worked on the staircase: think about the last thing that happened, which here means the last character of each string. Either those two characters are equal, in which case you may as well match them (that match costs nothing and can only help) and the rest of the problem is the two strings with their last characters removed. Or they differ, in which case at least one of them is not in the answer, so you try dropping each in turn and keep the better result. Write for the answer on the first characters of and the first of , and that reasoning is a recurrence:
The subproblem now has two moving parts, so the table is a grid rather than a row, with cells filled in time. Everything else is identical to the staircase: an honest recurrence, base cases along the edges, and each cell built from cells already filled (above, to the left, and diagonally back). And the reconstruction habit from the last section applies unchanged. Walk backwards from the bottom-right corner: on a match, take the character and step diagonally; otherwise step whichever way the value came from.
The two conditions that make it work
Step back and dynamic programming stops being a bag of tricks and becomes a diagnosis with two symptoms. The first is optimal substructure: the best answer to the whole is built from best answers to its parts. Fibonacci has it by definition; shortest coin counts have it because an optimal way to make is an optimal way to make some , plus one coin. The second is overlapping subproblems: those parts are not all distinct, the same few keep recurring, so solving each once and storing it pays off. When both hold, you have a choice of two doors into the same room. Go top-down and memoize the natural recursion, letting the cache prune the tree; or go bottom-up and tabulate, ordering the subproblems so every answer is waiting when you need it.
Which door you take is mostly taste and circumstance. Memoization keeps the code shaped like the mathematics and only ever computes subproblems you actually reach, which is a real saving when the reachable set is sparse. Tabulation gives up the recursion but wins a flat loop, easy constant-space tricks, and no risk of blowing the stack. Both turn the same exponential waste into linear work by refusing, exactly once per subproblem, to solve the same thing twice. That refusal is the entire idea. Everything else is where you choose to keep the notebook.
Exercises
In the naive
fib(6)tree, how many times doesfib(2)get computed from scratch? How many timesfib(1)? You can read both counts straight off the plate above by stepping through the naive tree, or reason them out. Say in one sentence why memoization brings the first count down to one but leaves thefib(1)leaves alone.The memoized
fibabove passesmemoalong as an argument. A tempting shortcut is to writedef fib(n, memo={}):and skip theif memo is Nonedance. Explain what goes wrong when this function is called several times in one program, and why the default argument is the culprit. (This is one of Python’s most famous footguns.)Take the coin denominations 1, 3, 4 and the amount 6, where greedy returned three coins. Trace
min_coins([1, 3, 4], 6)by hand: write outbest[0]throughbest[6]in order and show the entry where the table beats greedy. Then name the property greedy assumed and the coin system violated.Write
climb_stairs(n), the number of distinct ways to climb an n-step staircase taking 1 or 2 stairs per stride. The last stride reached the top from step or step , so the recurrence is the Fibonacci one in disguise. Build a table from the bottom up (do not recurse naively, the checks include ) and return the count. Run to grade against five sizes.The checks · run against your code
# climb_stairs(0) is 1 (one way: stand still) assert climb_stairs(0) == 1 # climb_stairs(1) is 1 assert climb_stairs(1) == 1 # climb_stairs(2) is 2 (1+1 or 2) assert climb_stairs(2) == 2 # climb_stairs(5) is 8 assert climb_stairs(5) == 8 # climb_stairs(10) is 89 assert climb_stairs(10) == 89
python runs in your browser · first run downloads ~240 kbPlate VII STAIRS, TABULATED · Implement climb_stairs(n) bottom-up. The ways to reach step are the ways to reach plus the ways to reach , with one way to stand at the bottom. Run to grade against five sizes. Hint one
Handle the tiny cases first: there is exactly one way to be at step 0 (do nothing) and one way to reach step 1. For everything above, each step’s count is the sum of the two below it.
Hint two
Make an array
waysof length , setways[0] = 1and, when ,ways[1] = 1, then loop i from 2 to n fillingways[i] = ways[i - 1] + ways[i - 2]. Watch the n = 0 case so you do not index past the end.The solution
A textbook bottom-up table. Guard n = 0 so the array is never indexed out of range, then walk up:
def climb_stairs(n): if n == 0: return 1 ways = [0] * (n + 1) ways[0] = 1 ways[1] = 1 for i in range(2, n + 1): ways[i] = ways[i - 1] + ways[i - 2] return ways[n]The counts are 1, 1, 2, 3, 5, 8, 13, …, which is Fibonacci shifted by one: climb_stairs(n) is fib(n + 1). You could return
fib_fast(n + 1)and pass every check in constant space, which is the same “how little of the table do I need?” trick from the tabulation section, one more time.Beat the greedy. Write
coin_change(coins, amount), the fewest coins from the given denominations that add up to exactlyamount, using each denomination as often as you like, and-1when no combination reaches it. Build a table; the checks include two systems where grabbing the biggest coin gives the wrong answer, and one amount that cannot be made at all. This is the same recurrence as the staircase with the strides given to you at runtime.The checks · run against your code
# the US system, where greedy happens to be right too assert coin_change([1, 5, 10, 25], 63) == 6 # the system where greedy is wrong: 3 + 3 beats 4 + 1 + 1 assert coin_change([1, 3, 4], 6) == 2 # zero needs no coins at all assert coin_change([1, 5], 0) == 0 # an amount no combination can reach assert coin_change([2, 5], 3) == -1 # an amount that is exactly one coin assert coin_change([7, 11], 11) == 1 # another greedy trap: 7 + 7 beats 10 + 1 + 1 + 1 + 1 assert coin_change([1, 7, 10], 14) == 2 # order of the denominations must not matter assert coin_change([4, 3, 1], 6) == coin_change([1, 3, 4], 6)
python runs in your browser · first run downloads ~240 kbPlate VIII COIN CHANGE, GRADED · best[a] is the fewest coins that make a, built from smaller entries that are already final. Run to grade against seven checks, including the 1, 3, 4 system where greedy fails, an unreachable amount, and a check that the order of the denominations does not matter. Hint one
Make a list
bestof lengthamount + 1. Setbest[0] = 0, because zero cents takes zero coins, and set every other entry to a sentinel that means “not reachable yet”. Any number bigger thanamountworks as the sentinel, since no answer can ever need more coins than there are cents.Hint two
Then walk
afrom 1 up toamount, and for each coincthat is not larger thana, consider paying with it: that costsbest[a - c] + 1. Keep the smallest such candidate. At the end,best[amount]is either a real count or still the sentinel, and the sentinel is what you translate into-1.The solution
Two nested loops, amounts on the outside and denominations on the inside, so every cell is built only from cells that are already final:
def coin_change(coins, amount): INF = amount + 1 # a sentinel meaning "unreachable" best = [0] + [INF] * amount for a in range(1, amount + 1): for c in coins: if c <= a and best[a - c] + 1 < best[a]: best[a] = best[a - c] + 1 return best[amount] if best[amount] <= amount else -1The cost is , which is a good deal more work than greedy’s single pass, and it is correct for every coin system rather than for the lucky ones. Notice that
coin_change([1, 5], 0)passes with no special case: the loop simply never runs andbest[0]is already 0. Add achoicearray, as in Plate V, and the same table will also tell you which coins.Two dimensions. Write
lcs_length(s, t), the length of the longest common subsequence of two strings. Build the grid:len(s) + 1rows,len(t) + 1columns, row 0 and column 0 all zeros. Then fill it with the recurrence from the LCS section, matching characters stepping diagonally and mismatches taking the better of the two neighbours. The checks include both empty strings, a pair with nothing in common, and a pair whose answer is not contiguous in either string.The checks · run against your code
# a shared prefix assert lcs_length("ABCD", "ABEF") == 2 # nothing in common assert lcs_length("abc", "xyz") == 0 # an empty string shares nothing with anything assert lcs_length("", "anything") == 0 assert lcs_length("anything", "") == 0 # the textbook instance: GTAB assert lcs_length("AGGTAB", "GXTXAYB") == 4 # the subsequence need not be contiguous assert lcs_length("STORRS", "SORROW") == 4 # a string against itself is all of itself assert lcs_length("husky", "husky") == 5 # the answer does not depend on which string you pass first assert lcs_length("AGGTAB", "GXTXAYB") == lcs_length("GXTXAYB", "AGGTAB")python runs in your browser · first run downloads ~240 kbPlate IX LCS, GRADED · Fill a two-dimensional table where L[i][j] answers the question for the first i characters of s and the first j of t. Run to grade against eight checks, including the empty string, disjoint alphabets, and the symmetry of the answer under swapping the two inputs. Hint one
Build the grid with a comprehension:
L = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]. The zero row and zero column are already correct and you never have to touch them again, which is the whole reason the table is one bigger than each string in each direction.Hint two
Loop
ifrom 1 tolen(s)andjfrom 1 tolen(t). Careful with the offset: cell[i][j]is abouts[i - 1]andt[j - 1], nots[i]andt[j]. If those two characters are equal, the cell is the diagonal neighbour plus one; otherwise it is the larger of the cell above and the cell to the left. Return the bottom-right corner.The solution
The whole recurrence is four lines, and the row and column of zeros do all the base-case work:
def lcs_length(s, t): L = [[0] * (len(t) + 1) for _ in range(len(s) + 1)] for i in range(1, len(s) + 1): for j in range(1, len(t) + 1): if s[i - 1] == t[j - 1]: L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j], L[i][j - 1]) return L[len(s)][len(t)]Time and space are both . The space can be cut to by the rolling trick from earlier, since each row is built only from the row above it and the cell to the left, so two rows are enough. But note what you lose: with only two rows alive you can still report the length and can no longer walk the table backwards to reconstruct the subsequence. That is the memo-versus-table tradeoff in its sharpest form, and it is why real diff implementations either keep the whole grid or use a cleverer algorithm entirely.
The main event. Write
knapsack(items, capacity), whereitemsis a list of(weight, value)pairs: choose a subset of total weight at mostcapacitywith the largest possible total value, and return that value. Each item may be taken at most once. This is the problem that punishes greedy hardest, because the item with the best value-per-kilogram can be exactly the wrong first choice, and one of the checks is built to catch you doing it.The checks · run against your code
# a zero capacity holds nothing assert knapsack([(2, 3), (3, 4)], 0) == 0 # one item that fits exactly assert knapsack([(2, 3)], 2) == 3 # one item that does not fit assert knapsack([(5, 100)], 4) == 0 # the textbook instance: weights 3 and 4 fill the bag for value 9 assert knapsack([(1, 1), (3, 4), (4, 5), (5, 7)], 7) == 9 # an item may be taken at most once, even if it would fit three times assert knapsack([(3, 5)], 9) == 5 # the density trap: two lighter items beat the one with the best ratio assert knapsack([(6, 30), (5, 20), (5, 20)], 10) == 40 # an empty shelf is worth nothing assert knapsack([], 10) == 0
python runs in your browser · first run downloads ~240 kbPlate X 0/1 KNAPSACK, GRADED · Add one item at a time to a table indexed by remaining capacity. Run to grade against seven checks: a zero capacity, an item that does not fit, the textbook four-item instance, an item that must not be reused, and the density trap where two lighter items beat the best ratio. Hint one
Start with the two-dimensional version if it helps you think:
best[i][c]is the most value you can get from the firstiitems in capacityc. For each item you have exactly two options, take it or leave it, so the cell is the larger ofbest[i - 1][c](leave it) andbest[i - 1][c - w] + v(take it, if it fits).Hint two
Once that works, notice that row
ionly ever reads rowi - 1, so one row will do. But there is a trap: if you sweep capacities upward while overwriting in place, the cell you read for “take it” may already include this same item, and you will have taken it twice. Sweep the capacities downward, fromcapacitytow, and every cell you read is still from the previous item’s row.The solution
One row, one item at a time, capacities descending. The direction of that inner loop is the entire difference between 0/1 knapsack and the unbounded version:
def knapsack(items, capacity): best = [0] * (capacity + 1) for w, v in items: for c in range(capacity, w - 1, -1): # DOWNWARD: no item twice if best[c - w] + v > best[c]: best[c] = best[c - w] + v return best[capacity]The cost is time in space. That looks polynomial and is not quite: the running time is proportional to the capacity’s value, not to the number of digits it takes to write it, so doubling the number of bits in the capacity doubles the running time again. Algorithms with that shape are called pseudo-polynomial, and 0/1 knapsack is the classic one; it is NP-hard in general, and this table is a genuine solution only because the capacity is small enough to index an array with. Reverse the inner loop to ascend and you have solved a different, easier problem, the one where every item is available in unlimited supply, which is exactly the coin problem from two exercises ago.