Nib asked for
Fewest Coins, Step by Step
Any new problem becomes a table once you say what one entry means, how it depends on smaller entries, and where it starts; for fewest coins, best(a) = 1 + the minimum of best(a − c) over every coin c.
7 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1two ways
Take a fresh problem: coins worth 1, 4, and 5, and a target of 8. What is the fewest coins that add up to exactly 8? Grabbing the biggest coin first gives 5+1+1+1, four coins, but 4+4 uses only two. A quick instinct can fail, so we need a method that checks the options.
A fresh problem needs a method, not a hunch.
a common mix-upAlways grabbing the biggest coin gives the fewest coins.
With coins 1, 4, 5, how many coins does 4+4 use for 8, and how many does biggest-first use?
Show the answer
4+4 uses 2 coins; biggest-first (5+1+1+1) uses 4.
2define the box
Step one: decide what a single table entry means, in plain words. Here, entry a holds the fewest coins needed to make exactly amount a. This one sentence is the whole design. Everything after it is bookkeeping, and the final answer is simply the entry at 8.
First, say in words what one entry means.
3look back
Step two: write how one entry depends on smaller ones. To make amount a, the last coin you add is some coin c, leaving a − c to make. The best way to do that is box a − c, so using coin c costs 1 + box(a − c). You don't know which coin is last, so try all of them.
Last coin c costs 1 plus the best for what's left.
If the last coin is a 4 and the amount is 8, which smaller box do you look at?
Show the answer
Box 4, since 8 − 4 = 4.
4the formula
The recipe, then: box a equals 1 plus the minimum of box(a − c) across every coin c that fits, meaning c is no larger than a. Compare this to page 5: the same smaller questions recur across different amounts, and the best answer for a is built from best answers for smaller amounts. That is why the trick applies here.
best(a) = 1 + min over coins c of best(a − c).
5base case
Step three: set the base case, the entry that needs no smaller entries. Making amount 0 takes zero coins, so box 0 holds 0. Without it the formulas would have nothing to start from, just as a recursive function needs a stopping case.
Base case: amount 0 needs 0 coins.
a common mix-upThe base case is an arbitrary detail; in fact every other entry rests on it.
6fill it in
Step four: fill in order, smallest amount first, so every box you need is already filled. For each box, check every coin and keep the smallest result; this is not a greedy pick of one coin, it is a minimum over all of them. Box 1 is 1. Box 2 is 2. Box 3 is 3. Box 4 is 1, from the 4 coin. Box 5 is 1. Box 6 is 2 (5+1). Box 7 is 3 (for example 5+1+1, or 4+1+1+1 costs more, so 3 wins). Box 8: using coin 1 gives 1 + box 7 = 4, using coin 4 gives 1 + box 4 = 2, using coin 5 gives 1 + box 3 = 4. The minimum is 2.
For each box, try every coin and keep the smallest.
What are the table values for boxes 4, 5, and 6?
Show the answer
1, 1, and 2.
7the recipe
Notice what you just did: the same four steps solve any problem of this kind. Say what an entry means, write how it depends on smaller entries, set the base case, fill in order. Fibonacci was this recipe with a simpler dependency, and fewest coins is the same recipe with a minimum added.
Meaning, dependency, base case, fill order: the recipe for any new problem.
Dynamic programming is not a bag of tricks: it is four questions you can ask of any problem, and a table that answers them.