Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture VII of XIV

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 2n2^n.

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.

Recursive calls to compute fib(n), naive versus top-down memoized, for n from 4 to 8. The naive count grows exponentially; the memoized count grows linearly.
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.

Plate I THE MEMOIZATION HEAT MAP · The fib recursion tree, drawn with the memo off and on. Toggle Naive versus Memoized and press Step to reveal it call by call; the counter climbs like 2n2^n on the left, but with the memo on, each repeated subproblem turns green and stops there, and the count settles to 2n−12n - 1. Flip on Heat map to shade every node by how often its subproblem is requested, fib(1)\text{fib}(1) and fib(2)\text{fib}(2) running hottest, with each node printing that count. Change n with the steppers. Idealised call counts, not CPU timings.

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 2n−12n - 1 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.

python runs in your browser · first run downloads ~240 kb
Plate II NAIVE VERSUS MEMOIZED, COUNTED · Press Run. The left column is the number of naive calls; the right is the memoized count, tallied by a counter the functions bump on every entry. By n=10n = 10 the naive tree is doing 177 calls to the memo's 19.

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 O(n)O(n) to O(1)O(1).

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 nn are exactly the routes to step n−1n - 1 plus the routes to step n−2n - 2:

ways(n)=ways(n−1)+ways(n−2),ways(0)=ways(1)=1.\text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2), \qquad \text{ways}(0) = \text{ways}(1) = 1.

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.

python runs in your browser · first run downloads ~240 kb
Plate III THE UNION STEPS · Routes up a twelve-step flight, counted top-down with a notebook and bottom-up with a table. Press Run: the two answers agree, and the last line shows the order the notebook was written in. The recursion asks in decreasing order and answers in increasing order, which is the table's order, arrived at the long way round.

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, O(n)O(n) 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.

python runs in your browser · first run downloads ~240 kb
Plate IV THE SPACE LEDGER · The same count in strides of 10 or 25 up to step 100, once with a memo and once with a full table, each reporting how many cells it kept. Press Run and compare the two numbers, then read the list of steps the memo ever visited. The last line is the other direction: when every cell is needed, how few must be alive at once.

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 O(1)O(1). 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 O(n)O(n) 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.

python runs in your browser · first run downloads ~240 kb
Plate V COINS, WITH THE RECEIPT · plan_coins fills best[a] and choice[a] together, then walks the choices backwards to name the actual coins. Press Run: on the 1, 3, 4 system greedy grabs a 4 and needs three coins while the table names 3 and 3, and on the 1, 7, 10 system greedy is worse still. The last row is a system where the amount cannot be made at all.

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 L(i,j)L(i, j) for the answer on the first ii characters of ss and the first jj of tt, and that reasoning is a recurrence:

L(i,j)={0i=0 or j=0,L(i−1,j−1)+1si=tj,max⁡(L(i−1,j), L(i,j−1))otherwise.L(i,j) = \begin{cases} 0 & i = 0 \text{ or } j = 0,\\ L(i-1,j-1) + 1 & s_i = t_j,\\ \max\bigl(L(i-1,j),\ L(i,j-1)\bigr) & \text{otherwise.} \end{cases}

The subproblem now has two moving parts, so the table is a grid rather than a row, with (m+1)(n+1)(m+1)(n+1) cells filled in O(mn)O(mn) 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.

python runs in your browser · first run downloads ~240 kb
Plate VI THE GRID, PRINTED · The LCS table for STORRS against SORROW, filled row by row and printed as a grid, then walked backwards to recover the subsequence itself. Press Run and read the bottom-right corner, then trace the walk by hand: a diagonal step means a matched letter, a sideways or upward step means a discarded one. Edit the two words and run again.

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 aa is an optimal way to make some a−ca - c, 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

  1. In the naive fib(6) tree, how many times does fib(2) get computed from scratch? How many times fib(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 the fib(1) leaves alone.

  2. The memoized fib above passes memo along as an argument. A tempting shortcut is to write def fib(n, memo={}): and skip the if memo is None dance. 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.)

  3. 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 out best[0] through best[6] in order and show the entry where the table beats greedy. Then name the property greedy assumed and the coin system violated.

  4. 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 n−1n - 1 or step n−2n - 2, so the recurrence is the Fibonacci one in disguise. Build a table from the bottom up (do not recurse naively, the checks include n=10n = 10) 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 kb
    Plate VII STAIRS, TABULATED · Implement climb_stairs(n) bottom-up. The ways to reach step ii are the ways to reach i−1i - 1 plus the ways to reach i−2i - 2, 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 ways of length n+1n + 1, set ways[0] = 1 and, when n≥1n \ge 1, ways[1] = 1, then loop i from 2 to n filling ways[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.

  5. Beat the greedy. Write coin_change(coins, amount), the fewest coins from the given denominations that add up to exactly amount, using each denomination as often as you like, and -1 when 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 kb
    Plate 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 best of length amount + 1. Set best[0] = 0, because zero cents takes zero coins, and set every other entry to a sentinel that means “not reachable yet”. Any number bigger than amount works as the sentinel, since no answer can ever need more coins than there are cents.

    Hint two

    Then walk a from 1 up to amount, and for each coin c that is not larger than a, consider paying with it: that costs best[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 -1

    The cost is O(amount×∣coins∣)O(\text{amount} \times |\text{coins}|), 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 and best[0] is already 0. Add a choice array, as in Plate V, and the same table will also tell you which coins.

  6. Two dimensions. Write lcs_length(s, t), the length of the longest common subsequence of two strings. Build the grid: len(s) + 1 rows, len(t) + 1 columns, 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 kb
    Plate 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 i from 1 to len(s) and j from 1 to len(t). Careful with the offset: cell [i][j] is about s[i - 1] and t[j - 1], not s[i] and t[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 O(mn)O(mn). The space can be cut to O(min⁡(m,n))O(\min(m, n)) 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.

  7. The main event. Write knapsack(items, capacity), where items is a list of (weight, value) pairs: choose a subset of total weight at most capacity with 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 kb
    Plate 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 first i items in capacity c. For each item you have exactly two options, take it or leave it, so the cell is the larger of best[i - 1][c] (leave it) and best[i - 1][c - w] + v (take it, if it fits).

    Hint two

    Once that works, notice that row i only ever reads row i - 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, from capacity to w, 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 O(n⋅capacity)O(n \cdot \text{capacity}) time in O(capacity)O(\text{capacity}) 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.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.