Coin Change
Fewest coins for amount a = 1 + min over coins c of best(a - c); ways variant counts combinations.
Decision · step 2 of 8DP in One Row: Fewest coins for 6 from 1, 3, 4
Amount 1. 1: 1 + dp[0] = 1. Keep the smallest: dp[1] = 1, ending with a 1 coin.
What you will see
For each amount, arrows reach back one coin value each; the minimum wins.
Cost
| Best | O(a * c) |
|---|---|
| Average | O(a * c) |
| Worst | O(a * c) |
| Space | O(a) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
Related
Variants
- Minimum Coins Minimize count.
- Count Ways Count combinations; iterate coins in the outer loop.
Taught by the same lesson
DP in One Row covers these too, in the same run.