Coin Change (LC 322) answered two ways at once. Up top, greedy builds
its stack the way everyone’s first instinct does: largest coin that fits,
repeat. Below it, the one-dimensional DP table fills one cell per tick,
each cell asking “one coin more than the cheapest sub-amount a single coin
reaches back to” — and the reach is drawn, an arc from dp[a] to
dp[a − c] for every coin that fits, the winning one bold in that coin’s
colour. When the table is full, the arrows are walked back from the amount
to zero and the coins they name are laid down as a second stack on the same
number line, so the two answers sit one above the other in the same units.
The point of the piece is the default. On US denominations the two stacks
agree, every time, on every amount — and the demo lets you sit in that
agreement long enough to believe greedy is safe. Then switch to {1, 3, 4}
and ask for 6: greedy takes 4 and pays two 1s while the table reaches
through 3 + 3 and lands a coin lower. A marker drops on the first amount
where greedy and the table disagree for whatever coin system is loaded, so
“greedy is wrong here” stops being a footnote and becomes a cell you can
point at in an interview. {1, 6, 10} for 24 is the dramatic one (greedy 6
coins, optimal 4); {3, 4} for 6 shows greedy stranding a remainder the
coin system can cover; {2} for 3 shows the ∞ that becomes the −1.
Reuse
src/change.js is a framework-free ES module:
greedyChange(coins, amount)— largest-first; returns the coins taken, the count, and any stranded remainder.dpChange(coins, amount)— the bottom-up table with a back-pointer per cell (from[a], the coin the minimum came through) and the optimal stack walked out of it. Ties go to the larger coin so the DP’s stack looks as much like greedy’s as the answer allows.firstDivergence(coins, maxAmount)— the smallest amount where greedy’s count differs from the optimum (or greedy strands a remainder), ornullwhen the coin system is canonical that far.candidates(coins, dp, a)— the sub-answers one cell weighs, for narrating a fill step.simulate(coins, amount)— the race as frames: greedy placing one coin per tick, then the table filling one cell per tick, then the arrows walked back. Same trace-per-tick shape asrho,sift,windowandastar-grid.
No rendering or timers in the module; the canvas demo is reference code.
Gotchas
- Amounts are capped at 40 and coin sets at 6 denominations, purely so the table stays readable as cells; the algorithm has no such limit.
- The demo bundles its own copy of
change.js(self-contained by contract); re-copy after editingsrc/.