The idea: two ways to pay with the fewest coins
You must pay an amount A with coins of given values, using as many of each as you like, and you want the fewest coins. The page runs two methods on the same coins and amount, in lockstep. On the left, greedy keeps taking the largest coin that still fits. On the right, dynamic programming (DP) fills a table with the best answer for every amount from 0 up to A. Each Step does one check of greedy and one cell of the table, so you can see how much work each one does.
Greedy: the largest coin first
Greedy sorts the coins from largest to smallest and looks at one coin at a time. If the coin fits in the amount left, it takes it and looks at the same coin again; if not, it moves on to the next smaller coin. One check is one "does this coin fit?" question. For US coins and 63 cents that is 9 checks: 25, 25, (25 no), 10, (10 no), (5 no), 1, 1, 1. Greedy needs no table, only the amount left. (Demo: US coins 1, 5, 10, 25 for 63)
For coin systems like the US and euro coins, greedy is always optimal. Such systems are called canonical. Many coin sets are not: with coins 1, 3, 4 and amount 6, greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 needs only 2. With 1, 7, 10 and amount 14, greedy takes 10 + 1 + 1 + 1 + 1 (5 coins) instead of 7 + 7. Greedy never takes a coin back, so one big coin early can force many small ones later. (Demo: coins 1, 3, 4 for 6; Demo: coins 1, 7, 10 for 14)
Without a 1-coin, greedy can even get stuck: with coins 3, 4 and amount 6 it takes the 4, and no coin fits the 2 that is left, although 3 + 3 works. (Demo: coins 3, 4 for 6)
DP: the table, bottom up
Think of the last coin of a best answer for amount a. If it is the coin c, the other coins pay a − c, and they must do it with the fewest coins too. We don't know which coin is last, so we try every one:
dp[0] = 0, dp[a] = 1 + min over coins c ≤ a of dp[a − c]
The table is filled from dp[1] up to dp[A], so every dp[a − c] it reads is already known (the light blue cells; the green one is the smallest). An amount that can't be made at all gets ∞. Each cell also remembers which coin gave the minimum. When the table is full, a trace back starts at dp[A], takes that cell's coin, jumps to dp[A − coin] and repeats until it reaches dp[0]; the coins on the way are the answer.
![The DP table for coins 1, 3, 4 from dp[0] to dp[6]: values 0, 1, 2, 1, 1, 2, 2 with last coins 1, 1, 3, 4, 4, 3. dp[6] reads dp[5] = 2, dp[3] = 1 and dp[2] = 2 and takes 1 + 1 = 2 through dp[3]. The trace back goes from dp[6] with coin 3 to dp[3], with coin 3 to dp[0].](Images/greedyvsdpcoins/dp-table.svg)
DP is always optimal, but it pays for it. It fills A cells and reads up to one cell per coin for each, so about A × k checks for k coins, and it keeps A + 1 numbers. For 63 cents with US coins that is 215 checks against greedy's 9, for the same 6 coins. The running time grows with the amount itself, not with its number of digits, which is called pseudo-polynomial.
The demos in numbers
| coins | amount | greedy | checks | DP | checks |
|---|---|---|---|---|---|
| 1, 5, 10, 25 | 63 | ✓ 25×2 + 10 + 1×3 = 6 | 9 | 6 | 215 |
| 1, 3, 4 | 6 | ✗ 4 + 1×2 = 3 | 5 | 3×2 = 2 | 13 |
| 1, 7, 10 | 14 | ✗ 10 + 1×4 = 5 | 7 | 7×2 = 2 | 27 |
| 3, 4 | 6 | ✗ stuck with 2 left | 3 | 3×2 = 2 | 7 |
| 1, 10, 25 | 30 | ✗ 25 + 1×5 = 6 | 8 | 10×3 = 3 | 57 |
The last row is the US system without the 5-cent nickel: removing one coin makes it non-canonical. (Demo: no nickel, 1, 10, 25 for 30)
When to pick which
| greedy | dynamic programming | |
|---|---|---|
| answer | optimal only for canonical coin systems | always optimal, or ∞ when the amount can't be made |
| work | about (number of coins taken + k) checks | about A × k checks |
| memory | the amount left | A + 1 table cells |
| use it for | cash registers and vending machines with real currencies | any coin set, stamps, "fewest steps to reach a total" puzzles |
A program can also test a coin system once and then use greedy safely. Kozen and Zaks showed that if greedy fails for some amount, it already fails for an amount smaller than the sum of the two largest coins. So it is enough to compare greedy with DP for every amount below that sum: below 7 for 1, 3, 4 (it fails at 6), below 35 for 1, 10, 25 (it fails at 30).
See also Making Change (greedy, recursion, memoization and the table on one page) and Coin Change (Number of Ways), which counts the ways to pay instead of the fewest coins.
How the DP table relates to top-down memoization is shown in Plain Recursion vs Memoization vs Tabulation.
Greedy strategies are provably optimal for other problems, such as activity selection and Huffman codes.
What the page leaves out
Amounts are capped at 80 so the whole table fits on the canvas. The page leaves out limited supplies of each coin (a bounded knapsack), the faster polynomial test for canonical systems (Pearson's algorithm), the memoized top-down version of the same recurrence, saving memory by keeping only the last cmax cells, and greedy strategies that are provably optimal for other problems, such as activity selection and Huffman codes.