Coin change

The problem it solves

Make an amount from coin denominations using as few coins as possible. It sounds like a cashier’s reflex — hand over the biggest coin that fits, repeat — and for the coins in your pocket that reflex happens to be right. That coincidence has ruined more interviews than any hard algorithm: with denominations {1, 3, 4} and a target of 6, the reflex takes 4, then 1, then 1 — three coins — while the right answer is 3 + 3, two. Greedy is not “usually fine” here; it is wrong in a way that no amount of tie-breaking fixes, because the mistake happens at the first coin and nothing downstream can unspend it.

Coin change is the canonical entry point to optimisation DP for exactly this reason: it is the smallest problem where you can feel why remembering answers to subproblems beats committing to plausible-looking choices. The same table shape then carries you to knapsacks, edit distances, jump games, and half the medium-tier interview canon. And its counting cousin — how many ways to make the amount — is one changed operator away, which the follow-ups return to.

The intuition — and where it breaks down

The DP’s idea in one sentence: the fewest coins for amount a is one more than the fewest coins for a minus some coin — whichever coin makes that smallest. You do not know which coin the optimal solution uses last, so you try all of them and keep the best; and the subamounts you need are smaller, so you can fill them in first and look them up rather than recompute.

The table drawn by the player is that idea with a second axis. Rows are “toolkits”: row i means “using only the first i coin kinds”. A cell asks one binary question — does adding this coin kind to the toolkit improve this amount? — and answers it by comparing two already-known numbers: the cell directly above (best without the coin) and the cell in the same row, one coin-width to the left (best using at least one of it). No guessing, no regret, no cleverness. The intuition breaks down in the places worth naming: the “one more than a smaller amount” recurrence silently assumes coins can be reused — the same-row lookup is precisely reuse, and moving that lookup one row up would turn this into 0/1 knapsack. And “smaller subproblems first” assumes amounts are non-negative integers; give it real-valued denominations and the table’s columns stop existing.

Loading…

A walkthrough you can check

Coins {1, 3, 4}, amount 6 — the greedy-killer. Row by row:

1. Row 1 (just 1s): every amount a costs a coins. dp = 0,1,2,3,4,5,6.
2. Row 2 (add 3): amount 3 asks — copy above (3 coins) or use a 3 (1 + dp[0] = 1)? Takes 1. Amount 6: above says 6; use-a-3 says 1 + dp[3] = 2. Takes 2.
3. Row 3 (add 4): amount 6 asks — above says 2; use-a-4 says 1 + dp[2] = 1 + 2 = 3. Keeps 2.

Final answer 2, via 3 + 3, and you can watch the reconstruction walk light exactly those two cells. Now run greedy mentally from 6: takes the 4 (subamount 2), then 1, then 1 — three coins, because taking the 4 stranded an amount that the 3s cover badly. The table never committed to the 4; it merely scored it and found it wanting.

The “unreachable” preset is the other lesson: coins {2, 4}, amount 7. Every cell in column 7 stays ∞ to the very end — the table does not crash or guess on impossible inputs, it proves impossibility by exhaustion.

The invariant

When cell (i, a) is computed, every cell it reads is already final: the cell above was finished in the previous row, and the cell coin-widths left was finished earlier in this row. That ordering claim is the entire correctness of bottom-up DP — the recurrence is only valid if its inputs are answers, not works-in-progress.

The value-level invariant: dp[i][a] is exactly the fewest coins making a from the first i kinds (∞ if impossible). Induction on cells in fill order: the base column is 0 coins for amount 0; each cell takes the min over precisely the two ways an optimal solution can relate to coin i — uses none of them (above), or uses at least one (left by the coin, plus one). There is no third case, so the min is exact. Note what the invariant does not say: nothing about which coins, only how many — the which is recovered afterwards by walking the choices backwards, which the player animates as the final wash.

Complexity, derived

The table has (n+1)·(amount+1) cells and each costs O(1): two lookups, a comparison, a write. Time O(n·amount), space O(n·amount) — or O(amount) space with a single reused row, since only the current and previous rows are ever read.

Now the sentence interviewers wait for: this is pseudo-polynomial. “amount” is a number in the input; representing it takes log(amount) bits, so a running time linear in amount is exponential in the input’s size. Double the digits of the amount and the table doubles in width a thousandfold. For amounts in the thousands this is irrelevant; for amounts near 2⁶⁴ the algorithm is unusable, and no reordering of loops rescues it. Being able to say why O(n·amount) and “polynomial” are different claims — and why the same caveat applies to knapsack — is the depth marker this problem exists to test.

What people get wrong

• Trusting greedy because it works on canonical coinage. Whether greedy is correct is a property of the denomination set, and {1, 3, 4} is the two-line counterexample to memorise.
• Initialising with 0 instead of ∞: unreachable amounts then pretend to cost nothing, and every min() downstream leaks the lie. The ∞ is doing real work — the unreachable preset shows it surviving to the last cell.
• Reading the take-branch from the row above: that computes 0/1 coin change (each coin usable once), a different problem. Reuse lives in the same-row lookup; knowing which row each branch reads is knowing which knapsack you are solving.
• Confusing min-coins with count-ways: same table, different operator (min vs sum) and different base (0 vs 1). Mixing their bases produces confident nonsense.
• In the 1D version, iterating amounts in the wrong direction — forward allows reuse (correct here), backward forbids it (correct for 0/1). This one bug flips which problem you solved, silently.

Implementation notes

The 2D table shown is the teaching layout; production code uses one row of length amount+1, initialised to ∞ except dp[0]=0, with coins in the outer loop. The 2D↔1D correspondence is worth internalising: the 1D forward scan is exactly the same-row read that grants reuse.

Reconstruction without a parent array: walk from (n, amount); if the value equals the cell above, the coin was unused — go up; otherwise emit the coin and step left by its width. This re-derives the choices from the values, costing O(n + amount) and no extra memory — the player’s ending wash is this walk verbatim.

Two production notes. If you only need reachability (can the amount be made?), booleans suffice and the operator degenerates to OR — that is subset-sum’s engine. And when denominations are canonical and known to be, greedy is O(n log n) and fine; the point is that “canonical” is a checkable property (there are polynomial tests for it), not a vibe.

The follow-up questions

Why does greedy work for US coins but not {1, 3, 4}? Canonical systems have the property that each coin is worth at least as much as any optimal combination it could displace. {1, 5, 10, 25} satisfies it; {1, 3, 4} fails at 6. Greedy’s correctness is a theorem about the coin set — one that real currencies were (accidentally) designed to satisfy.

How does counting the ways differ? Replace min with sum, base with 1 way for amount 0, and mind the loop order: coins-outer counts combinations (3+3 once), amounts-outer counts permutations (3+3 and 3+3 “in both orders” — same thing here, but 1+3 vs 3+1 separately). Interviewers flip between the variants to test whether the table’s meaning is understood.

Can it run in O(amount) space? Yes — the recurrence reads only the current and previous rows, and with reuse allowed the previous row is only needed for the skip branch, so one array iterated per coin suffices.

What breaks with real-valued or huge amounts? Real values: the columns stop being enumerable — DP over amounts requires integer (or discretised) amounts. Huge amounts: pseudo-polynomiality bites; for astronomically large targets with few denominations, number-theoretic approaches (or BFS over residues mod the smallest coin) replace the table.