Overview
Coin Change asks for the fewest coins that add up to a target amount, given a set of denominations with unlimited supply of each. The dynamic-programming table answers it for every amount from 0 up to the target, building each answer from smaller ones already solved.
It earns its place in a catalogue mostly because of what it disproves. Handing out the largest coin that fits, over and over, is the intuitive method and the one real cashiers use — and it is wrong for some coin systems. With coins of 1, 3 and 4, making 6 greedily gives 4+1+1, three coins; the table finds 3+3, two coins. Vietnamese and most modern currencies happen to be canonical systems where greedy is safe, which is exactly why the failure is so easy to miss.
How Coin Change (DP) works
- Create an array of size amount + 1 and fill it with infinity, except position 0 which is 0 — no coins are needed to make nothing.
- For every amount a from 1 up to the target, consider each coin denomination in turn.
- If the coin is no larger than a, the candidate answer is 1 plus the stored answer for a − coin.
- Keep the smallest candidate across all coins and store it at position a.
- The final cell holds the answer, or infinity if the amount cannot be formed at all. To list the coins, store which denomination produced each cell and walk back.
When to use it
- Cash handling and change dispensing in point-of-sale systems and vending machines.
- Any 'minimum number of pieces to reach a total' problem: stamps, weights, packet sizes, quantised payments.
- Demonstrating why a greedy heuristic needs proof rather than intuition, since the counterexample is two lines long.
- As a stepping stone to the counting variant — how many distinct ways to make the amount — which uses the same table with the loops swapped.
Complexity analysis
Time is O(m·A) for m denominations and target amount A: every amount is visited once and every coin is tried against it. Space is O(A) for the one-dimensional table, or O(A) more if you also store the chosen coin for reconstruction. Like knapsack this is pseudo-polynomial — A is a value, not an input length — so a target in the billions is out of reach regardless of how few coins there are.
Frequently asked questions
When exactly does the greedy method work?
Only for canonical coin systems, and deciding whether a given system is canonical is a separate, non-obvious problem. Practical rule: if you did not choose the denominations yourself, do not assume greedy is safe — run the table.
How do you tell 'impossible' from 'zero coins'?
Position 0 is genuinely 0 and every unreachable amount stays at the infinity sentinel. Using 0 as the initial fill instead would silently report success for amounts that cannot be formed, which is a common bug in first implementations.
What changes if each coin can be used only once?
It becomes 0/1 knapsack. The fix is the same one: iterate the amount downwards so a coin already applied at a smaller amount is not reused within the same item's pass.