Coin change — every question, written out
Fewest coins to make an amount — the problem where greedy confidently gives the wrong answer and the DP table quietly delivers the right one.
Read the coin change explanation and watch it run
Coins {1, 15, 25} and a target of 30. What does greedy do, and what does the table do?
Trade-off & selection
Greedy takes 25 and then five 1s — six coins; the table finds 15 + 15, which is two
Greedy grabs the largest coin that fits and is then stuck making 5 out of pennies, six coins in total. The table never commits: at the final cell it prices the branch that spends a 25 at six coins, compares it with the two-coin answer already found without it, and keeps the smaller. The mistake happens at the very first coin, which is why no downstream repair can rescue it.
See it run — The last cell: 2 inherited from the row above, against 6 for the branch that spends the 25.
Greedy is right for the coins in your pocket. What property makes a denomination set safe?
Trade-off & selection
Canonicality: each coin is worth at least any optimal combination it could displace
Whether greedy is correct is a theorem about the coin set rather than about the algorithm, and it is checkable — there are polynomial tests for canonicality. Real currencies happen to satisfy it, which is why the cashier reflex feels universal when it is not. {1, 3, 4} at an amount of 6 is the two-line counterexample worth memorising, and the trap preset is its larger cousin.
What does filling this table cost in time and in space?
Complexity derivation
O(n · amount) for both — one constant-time cell per coin kind and amount
The table holds (n + 1) × (amount + 1) cells and each one does two lookups, a comparison and a write. That is O(n · amount) time and, as drawn, the same in space. Reducing the space to O(amount) is the standard next move, since only the current and previous rows are ever read.
Why is O(n · amount) called pseudo-polynomial rather than simply polynomial?
Complexity derivation
"amount" is a value, and writing it takes log(amount) bits — so this is exponential in the input size
Complexity is measured against the number of bits in the input, and writing the number 1,000,000 takes about twenty of them. Linear in the value is therefore exponential in the digits: add one digit to the amount and the table becomes ten times wider. Being able to say why O(n · amount) and "polynomial" are different claims — and that knapsack carries the same caveat — is the depth marker this problem exists to test.
So the amount is around a trillion and there are three denominations. What now?
Trade-off & selection
The table is unusable: this wants number theory or a search over residues, not more memory
Pseudo-polynomiality bites exactly here: the algorithm is linear in a number that is astronomically large, and no reordering of loops or trimming of rows changes that. With few denominations the structure is arithmetic rather than tabular — reasoning modulo the smallest coin, or searching over residues, replaces the sweep across amounts. Naming the boundary is a better answer than optimising up to it.
The 2D table collapses to one array of length amount+1. What makes that legal?
Complexity derivation
A cell reads only the row above and its own row, so one array per coin pass suffices
Only two rows are ever live, so a single array reused once per coin holds everything the recurrence needs. Because the take-branch reads the current row, a forward scan over amounts sees values already updated with this coin — which is exactly what grants unlimited reuse. That correspondence is worth internalising: the 1D forward scan *is* the same-row read of the 2D table.
What do the row index and the column index of this table actually mean?
Invariant identification
Row i means "only the first i coin kinds are available"; column a is the amount to make
Rows are toolkits and columns are targets: dp[i][a] is the fewest coins making amount a from the first i kinds, with ∞ standing for impossible. Each cell then asks one binary question — does adding this coin kind improve this amount? — answered by comparing the cell above with the cell one coin-width to the left. Prism announces every new row as "coin 3 joins the toolkit", which is the row axis stated in words.
See it run — A new row opens: coin 3 joins the toolkit, and every amount is asked again with it available.
Bottom-up DP rests on one ordering claim. State it for this table.
Invariant identification
Every cell a cell reads is already final: the one above from last row, the one left from this row
The recurrence is valid only when its inputs are answers rather than works in progress, and the loop order is what guarantees that: the row above finished a whole pass ago, and the cell `coin` columns to the left finished earlier in this pass. That is the entire correctness argument for bottom-up DP, and it is the thing memoised recursion gets free from the call stack. Break the order and the table still fills — with numbers derived from placeholders.
A candidate writes the take-branch as `dp[i-1][a - coin] + 1`. Which problem have they now solved?
Code diagnosis
0/1 coin change — each coin usable once — because the read jumped up a row
Reading `a - coin` from the current row means "I may already have used this coin", which grants unlimited copies; reading it from the row above means "at most one of this coin", which is 0/1 knapsack in coin clothing. Both are correct programs for different problems and neither crashes, so this is a bug only a test catches. Knowing which row each branch reads is knowing which knapsack you are solving.
The table is initialised to 0 everywhere instead of ∞. What goes wrong, and where?
Code diagnosis
Unreachable amounts pretend to cost nothing, and every later minimum inherits the lie
A sentinel has to be a value the domain cannot produce, and 0 is the honest cost of a real cell — amount zero. Seeding the rest with 0 tells the recurrence that impossible subamounts are free, and every minimum downstream takes that number and adds one to it. Prism uses ∞ and lets it survive to the last cell, which is what turns "no answer" into a proof rather than a shrug.
Coins {2, 4} and an amount of 7. What does the table do?
Edge case reasoning
Column 7 stays ∞ through every row, and the run reports −1
Even coins cannot sum to an odd amount, and the table establishes that by exhaustion rather than by insight: every odd column stays ∞ from the first row to the last. The ∞ is doing real work, because it is what makes unreachability propagate instead of quietly turning into a small number. The final cell is written empty and the run returns −1 — a proof of impossibility, not a failure to find something.
See it run — The last cell is written empty: ∞ survived all the way to (2, 7).
Why is the entire first column zero before any coin has been considered?
Edge case reasoning
Amount 0 needs no coins whatever the toolkit — it is the recurrence’s base case
Making nothing costs nothing, and it costs nothing regardless of which coins you hold — so the whole column is 0, not merely its first cell. Every take-branch eventually bottoms out there, which is what stops the recurrence from descending forever. The trace writes those cells first, one per row, before any coin joins the toolkit.
See it run — The base column being written: amount 0 costs 0 coins, on every row.
The same table can count HOW MANY ways make the amount. What has to change?
Comparison
Replace min with a sum, and the base with 1 — there is one way to make nothing
The two variants share a table shape and differ in their algebra: min over a base of 0 coins, or sum over a base of 1 way. Loop order matters more for counting than for minimising — coins in the outer loop counts combinations, amounts in the outer loop counts ordered sequences. Interviewers flip between them precisely to test whether the table’s meaning is understood or merely memorised.
Prism cross-checks its own answer with a BFS over amounts. Why is that the same problem?
Comparison
Amounts are nodes and coins are unit-weight edges, so fewest coins is a shortest path
Give each amount a node and draw an edge from `a` to `a + coin` for every denomination: all edges cost one coin, so fewest coins is the unweighted shortest path from 0, which is what BFS computes. Having two independent derivations of the same number is exactly why the reference implementation is written that way. Spotting "unit weights, so BFS" is worth having ready, because it turns some DP questions into three lines.
Coins {1, 3, 4}, amount 6. Cell (2, 6) is written as 2. Which two numbers produced it?
Trace prediction
Six from the row above, and one plus dp[2][3] — a second 3 on top of the first
The skip-branch is dp[1][6] = 6, the all-pennies answer without the 3. The take-branch is 1 + dp[2][3] = 1 + 1 = 2, and it reads the *same* row, which is what allows a second 3 to be used. The minimum of the two is written, and 3 + 3 has been discovered without anyone ever proposing it.
See it run — Cell (2, 6) takes the value 2 — the moment 3 + 3 appears, well before the final answer.
The last row adds coin 4, and cell (3, 6) still holds 2. Why does the 4 not help?
Trace prediction
Using a 4 costs 1 + dp[3][2] = 3, which loses to the 2 already found without it
Both candidates are computed: skipping gives dp[2][6] = 2, and using gives 1 + dp[3][2] = 3, because making 2 from {1, 3, 4} still needs two pennies. The cell keeps the minimum, so the 4 is scored and rejected rather than avoided. This is the exact cell where greedy went wrong — it would have spent the 4 without ever pricing the alternative.
See it run — The final cell copies 2 from above: the 4 was considered, priced at 3, and turned down.
Explain coin change, and why the obvious method fails, to someone who does not code. Say it out loud first.
Explain it plainly
Say you are giving change and you want to hand over as few coins as possible. The tempting method is the cashier’s: grab the biggest coin that still fits, then repeat. That is right for the coins in your pocket and wrong in general — with coins worth 1, 15 and 25 and a bill of 30, the reflex grabs the 25 and is then stuck making 5 out of pennies, six coins, while two fifteens would have done it in two. The problem is that the reflex commits: once the 25 is on the counter, nothing later can unspend it. So do something almost mechanical instead. Work out the cheapest way to make 1, then 2, then 3, and so on up to the target, writing each answer in its own box as you go. To fill the box for 30, you only ask one small question per coin you own: what did the box for "30 minus that coin" say, plus one for the coin itself? Take the smallest of those answers and write it down. Every box you need has already been filled by the time you need it, so nothing is ever guessed, and the answer for 30 is assembled out of answers you already trust. Where it stops being pretty: you have to fill a box for every single amount from 1 up to the target. Ask for change for a trillion and that is a trillion boxes, and the tidy method is suddenly the slowest thing in the room.
The listener should end up able to say why grabbing the biggest coin is a trap and what replaces it. A strong answer names the commitment problem, then the build-up-from-small-answers idea, and finally admits the cost — a box for every amount up to the target.