Coin change
To make an amount with the fewest coins, consider every coin you might hand over last. If you hand over a 5, you still have to make the amount minus five, and that answer is already in the table to the left. So the cell for an amount is one more than the smallest of the cells reachable by subtracting a single coin. The base case is zero, which needs no coins at all.
Its recurrence
C(a) = 1 + min over coins c of C(a − c)
When it is the right choice
Any "fewest pieces" question where the pieces can be reused: making change, cutting a length of pipe into fixed sizes, hitting a score with a fixed set of moves. Note that this is not the same problem as the greedy one — always taking the largest coin that fits works for ordinary currency and fails for sets like 1, 3 and 4, where making 6 greedily takes three coins and the table finds two. That failure is the reason this page exists rather than a greedy one.
How it works
- Make a row of cells, one for every amount from 0 up to the target.
- Write 0 into the cell for amount zero: no coins are needed to make nothing.
- For each amount in turn, try every coin that is not larger than it.
- Each coin points back to the cell for the amount minus that coin; one more than the best of those is this cell’s answer.
- Remember which coin gave the best answer, so the traceback can name it.
- Walk back from the target, subtracting the remembered coin each time, to read off the coins used.
Worth noticing
- The arrows reach back different distances on this page, one per coin, and that is the choice the recurrence contains. Fibonacci’s two arrows were always the same two neighbours; here the page is about picking one of several.
- A coin larger than the current amount is refused rather than tried, and the refused arrow is drawn as refused. That is not a special case bolted on: it is the recurrence’s own condition.
- An amount that cannot be made at all stays unfilled to the end, and the page says so instead of reporting a number. With coins of 3 and 5 there is no way to make 1, 2, 4 or 7.
Cost
- Best
- O(a · k)
- Average
- O(a · k)
- Worst
- O(a · k)
- Extra space
- O(a)
- Table
- one dimension
- Accepts
- 2 to 6 coins, each from 1 to 50; amount from 1 to 32
The limits are pedagogical rather than technical: this tool keeps the whole table in every recorded step, so the shape of the table sets the size of the trace directly, and a run has to stay short enough to sit and watch. An input that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the input sizes rather than by running it and finding out.
An unfilled cell is drawn differently from a cell holding a zero — no fill, a dashed outline, and no number at all — because early in a run that difference is most of the picture.