A First Taste of Algorithms · Recursion That Remembers

Sevenia, healed

Now the debt this book has carried since Chapter 2. Sevenia’s coins {1, 7, 10}; you owe 14; greedy grabbed the 10 and paid five coins for a two-coin debt. Time to make change correctly — for every amount, in any coin system whatsoever.

Ask the question in the staircase’s grammar. Let best(a) be the fewest coins paying amount a. Stand at amount a and look at your first decision: the first coin handed over is a 1, a 7, or a 10 — no fourth kind — and each choice leaves a smaller debt:

best(a) = 1 + min( best(a − 1), best(a − 7), best(a − 10) )

(only the options with a − c ≥ 0 compete, and the floor is best(0) = 0: no debt, no coins).

Put this next to greedy and the difference in character is the chapter’s real lesson. Greedy, at amount 14, looked at the three coins, judged the 10 best-looking, and committed — the 7-branch and the 1-branch were never priced. The recurrence refuses to commit: it prices every branch — what would the future cost after a 1, after a 7, after a 10 — and only then takes the min. Greedy is a verdict before the trial; dynamic programming insists on hearing every future testify. That refusal would be exponentially expensive done naively (three branches, branching again, the staircase’s tree all over). The notebook makes it cheap: only the amounts 0 through a exist as distinct questions, so the whole trial costs about a × (number of coin types) table entries.

Run the table bottom-up by hand for Sevenia to 14 — this is the wound actually closing, so do it slowly:

Watch the entry at 7 snap to 1, the entry at 10 snap to 1, and then the entry at 14: min(best(13), best(7), best(4)) + 1 = min(4, 1, 4) + 1 = 2. The table found 7 + 7 not by insight but by bookkeeping — the 7-branch was priced like every other branch, and the price was right there. In Lab 4 your DP changer faces your own Chapter 2 greedy across every amount to 100; greedy loses six times and DP never loses once, because DP cannot lose: the Diamond below has you prove its recurrence is not a heuristic but a theorem.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses