Dynamic Programming: Greedy That Keeps Receipts

Last week ended with greedy face-down on the floor: coins {1, 3, 4}, amount 6, and the sprinter confidently handing over three coins when two would do. This week we fix it — with the least glamorous idea in this course. Don't guess the first move. Answer every smaller amount first, write each answer down, and build the big answer out of the written ones. That habit has a fancy name, dynamic programming, and it cracks the coins, then a burglar's packing problem, then the "how alike are these two words?" question your spellchecker asks on every keystroke.

Session planHow we will spend the two sessions

Section 1Unfinished business

The scene of the crime, one more time. The coins are 1, 3 and 4, the amount is 6, and the rule is "fewest coins." Greedy grabs the 4 — the best-looking first move — and is sunk: 4 + 1 + 1, three coins, when 3 + 3 does it in two. The problem wasn't the arithmetic. The problem was committing to the first grab without knowing what it does to the rest of the job.

So here is the fix, and it is embarrassingly honest: refuse to answer 6 until you have answered everything smaller. Work out the fewest coins for amount 0, then 1, then 2, and so on up — and write every answer in a notebook as you go. By the time you reach 6, the question has become easy, because any first grab leaves a smaller amount, and every smaller amount is already written down.

Watch it happen. Each line below uses only lines already written:

Notice what happened to greedy's fatal flaw. Greedy committed to the 4 because it looked best and never checked what it did to the rest. The notebook also considers grabbing the 4 — but then it looks up what the leftover 2 actually costs, instead of hoping. No grab gets trusted; every grab gets billed. That is the whole trick, and it is why we're calling this greedy that keeps receipts.

And look at the amount-5 line: the notebook says 2 coins (4+1) — exactly what greedy would have said. Greedy isn't always wrong; it just can't tell you when it's right. The notebook can, because it checked everything. Here it is as code — a dozen lines, always right, for any coin set on Earth:

def fewest_coins(coins, amount):
    """Fewest coins that make the amount — any coin set, always right."""
    best = [0] + [None] * amount          # best[a] = fewest coins for amount a
    for a in range(1, amount + 1):        # answer every amount, small to large
        for c in coins:                   # try every possible first grab
            if c <= a and best[a - c] is not None:
                option = best[a - c] + 1  # the grab, plus the looked-up rest
                if best[a] is None or option < best[a]:
                    best[a] = option      # write the winner in the notebook
    return best[amount]

print(fewest_coins([1, 3, 4], 6))   # 2 — the 3+3 greedy could never see

Section 2Write it down: the two ingredients

Strip away the coins and two things made that work. Every problem dynamic programming cracks has both, so learn them as a pair:

Why does the second ingredient matter so much? Because without the notebook, "built from smaller versions of itself" is a bomb. Here is the canonical horror story. The Fibonacci numbers are the simplest self-built sequence there is — each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13… The definition translates to code so directly it feels like cheating:

def fib(n):                        # the innocent-looking disaster
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

notebook = {}
def fib_memo(n):                   # the same thing, keeping receipts
    if n < 2:
        return n
    if n not in notebook:            # only compute what isn't written down
        notebook[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return notebook[n]

Run the innocent version on fib(35) and your laptop goes quiet for several seconds. Why? Draw what it actually does:

Put numbers on it, because the numbers are the lesson. Naive fib(35) makes about 30 million calls — several seconds of Python — to learn 35 numbers. The notebook version computes each of those 35 numbers once: instant. Ask for fib(50) and naive needs about 41 billion calls — hours — while the notebook writes 51 lines. By fib(100), the naive call count has 22 digits: tens of thousands of years even at a billion calls per second, versus 101 notebook lines. (The waste snowballs because the number of calls grows exactly like the Fibonacci numbers themselves — the recursion re-creates its own explosion.)

Section 3Two flavors, same dish

There are two ways to run the notebook, and you have now seen both without being told. They deserve names, because you will meet both in every DP you ever read:

Here is coin change again, top-down this time, so you can see both flavors on the same problem:

def fewest_coins_topdown(coins, amount, notebook=None):
    """Same answers as §1's version — recursion plus a notebook."""
    if notebook is None:
        notebook = {0: 0}                # amount 0 costs 0 coins
    if amount in notebook:                # already answered? look it up
        return notebook[amount]
    best = None
    for c in coins:                       # try every first grab
        if c <= amount:
            rest = fewest_coins_topdown(coins, amount - c, notebook)
            if rest is not None and (best is None or rest + 1 < best):
                best = rest + 1
    notebook[amount] = best               # write it down before returning
    return best

Same answers, always. Same amount of real work, too: each flavor answers every amount from 0 to the target exactly once, so both do "number of amounts × number of coins" small steps — for coins {1, 3, 4} and amount 6, that's 7 amounts × 3 grabs, about twenty tiny lookups in all. The differences are cosmetic: top-down reads like the problem statement and skips amounts that never come up; bottom-up has no recursion to trace and is usually a touch faster in practice. Pick whichever one you can read back without squinting. In this course, bottom-up tables will usually win that contest, and they make better pictures — as you're about to see.

Section 4The knapsack heist

New problem, same medicine. You are a burglar — a thoughtful burglar — standing in a mansion with a bag that holds 10 pounds. Around you is loot: each piece has a weight and a price tag. You can't take everything. The job: choose what goes in the bag so the total price is as high as possible without busting the 10-pound limit. Computer scientists call this the knapsack problem, and it is everywhere a budget is: shipping crates, ad slots, server memory, your weekend.

Greedy has an opinion, of course. "Take the best value per pound first!" It even sounds professional. Here is a three-item mansion that bankrupts it:

Sound familiar? It's the coin story wearing a ski mask. The grab that looks best right now poisons what's possible afterward, and greedy never checks. So apply the medicine. What's the "smaller version of the same problem" here? When you stand in front of one piece of loot, you have exactly two options, and each leaves you with a smaller heist:

For our heist that notebook is small: 5 pieces of loot (we'll add a vase and a jar of coins to the mansion), 0-to-10 pounds of room — a 6-row, 11-column grid, 66 little numbers, each one a single max-of-two-lookups. Sixty-six tiny sums to be certain about all 32 possible bags. Try the heist yourself first; then open the notebook and watch it not guess:

Some things to try:

1. Pack greedily by value per pound — painting first, then whatever fits. You'll land on $58. Now hunt by hand for something better before pressing the button. (There is something better.)
2. Press Show the notebook and watch the fill: every cell is just "skip (copy the cell above) or take (price + the cell above-and-to-the-left), whichever is bigger." No cell ever guesses.
3. When the fill ends, follow the blue trail backwards from the bottom-right cell. Wherever a cell differs from the one above it, that piece was taken. The notebook doesn't just know the best price — it remembers which items, for free.
4. Reset and try to beat $70. Report back when you give up.

And the code is shorter than the heist briefing:

def best_haul(items, room):
    """items: list of (weight, price). room: what the bag holds.
    rows[i][w] = best haul using only the first i items with w pounds of room."""
    rows = [[0] * (room + 1)]                 # row 0: no items yet — worth $0
    for weight, price in items:
        prev, row = rows[-1], []
        for w in range(room + 1):
            skip = prev[w]                     # don't take it: row above, same room
            take = prev[w - weight] + price if weight <= w else 0
            row.append(max(skip, take))        # the better future wins the cell
        rows.append(row)
    return rows[-1][room]

loot = [(6, 48), (5, 35), (5, 35), (3, 14), (2, 10)]
print(best_haul(loot, 10))   # 70 — jewelry + clock; the $8/lb painting stays

Section 5How alike are two words?

Last stop, and it's the one in your pocket. You type SUNDAY; your phone wonders if you meant SATURDAY. Before it can decide, it needs a number: how much do these two words have in common? The standard answer: find the longest run of letters that appears in both words in the same order — other letters may be crossed out, but the survivors can't be shuffled. That shared skeleton is called the longest common subsequence, and the same measurement, scaled up, is how DNA analysis decides how related two gene sequences are.

Could you find that by brute force? SUNDAY has 64 ways to cross out letters; check each against SATURDAY. Fine for words — fatal for DNA, where "words" run millions of letters and the cross-out count has more digits than the universe has atoms. Time for the medicine, and here is the lovely part: it's the same take-it-or-don't move from the heist. Look at the last letter of each word:

Smaller versions of the same question, asked over and over (the pair "SUND / SATU" gets asked by many different paths) — both ingredients present. So: notebook. This one is a grid, like the heist's: one row per letter of the first word, one column per letter of the second, and the cell at row i, column j answers "how long is the best skeleton of the first i letters versus the first j letters?" Each cell is one look at its three neighbors — diagonal if the letters match, the better of above/left if not. For SUNDAY vs SATURDAY that's a 7 × 9 grid: 63 tiny cells to settle all 64 × 256 possible cross-outs. Type any two words and watch:

Some things to try:

1. Fill SUNDAY vs SATURDAY. Gold cells are where the two letters match — watch the score tick up by exactly 1 from the diagonal at each one. The blue trail afterwards is the walk-back: every diagonal step on it donates one letter, and reading those letters off spells SUDAY.
2. Try SPRING vs STRING, then AAAA vs AKAKA. Predict the length before filling.
3. Try two words with nothing in common. The grid fills with zeros — the notebook saying "no skeleton," 63 receipts to prove it.

def longest_common(a, b):
    """grid[i][j] = longest shared skeleton of a's first i letters
    and b's first j letters."""
    grid = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:                 # last letters match:
                grid[i][j] = grid[i - 1][j - 1] + 1  # keep the letter, +1
            else:                                    # they can't both survive:
                grid[i][j] = max(grid[i - 1][j],     # shorten word a, or
                                 grid[i][j - 1])     # shorten word b
    return grid[len(a)][len(b)]

print(longest_common("SUNDAY", "SATURDAY"))   # 5 — S·U·D·A·Y

Section 6When to reach for DP

Three problems, one move. Time to bottle it. Reach for the notebook when all three of these are true:

And the honest one-line verdict on last week versus this week: greedy is just DP where you can prove the first grab is always safe — the swap test from Notes 08 is that proof. When the swaps go through, you get to skip the whole notebook and keep only the grab: that's why greedy is faster when it's right. When the swaps jam, the grab's value depends on what it leaves behind, and you pay for the notebook. Never the other way around: DP is the safe default, greedy is the earned shortcut.

To file this week into the personality gallery: greedy was the sprinter. Dynamic programming is the accountant. Unhurried, a little boring, writes everything down, audits every option — and is never, ever wrong about the total. (The name, for what it's worth, means nothing: Richard Bellman, who invented the method in the 1950s, later admitted he picked "dynamic programming" partly because it sounded too impressive for his funders to object to. "The notebook method" was taken, presumably.)

Section 7Before next session