DP: Coin Change
Medium+90 XPFewest coins to make an amount by building up a best-answer table, one amount at a time.
No visualization loaded.
Watch
—
Press Run to begin.
You have coins of a few values and want to make some amount using as FEW coins as possible. Instead of guessing, you build a table of answers from small amounts up to the target: dp[amount] = the fewest coins needed for that amount. To fill dp[amount], you try each coin: 'if I use this coin last, I still need dp[amount − coin] coins before it, plus this one.' Take the smallest result over all coins. Earlier answers are already solved, so each amount is decided instantly.
▸Why does dp[0] start at 0 and everything else at ∞?
dp[0]=0 because making the amount 0 needs zero coins — a free, true base case. Everything else starts at ∞ meaning 'we don't know how yet / impossible so far.' As we fill the table, real numbers replace the ∞'s; any cell still ∞ at the end means that amount can't be made.
▸What is the highlighted source cell when an amount lights up?
It's dp[amount − coin] — the answer to a SMALLER amount we already solved. Using one coin of value c to reach amount a means the rest (a − c) was already made optimally, so dp[a] = 1 + dp[a − c]. We test that for every coin and keep the minimum.
▸Why try every coin for every amount instead of always grabbing the biggest coin?
Greedily grabbing the biggest coin can fail. Coins {1,3,4} to make 6: greedy takes 4 then 1+1 = three coins, but 3+3 = two coins is better. Trying all coins at each amount and keeping the minimum is what guarantees the truly fewest.
▸How is this like Climbing Stairs?
Same engine: each cell is built from smaller cells you already filled, left to right. Climbing Stairs ADDS two earlier cells; Coin Change takes the MINIMUM over several earlier cells (one per coin) and adds 1. Different combiner, same 'solve once, reuse' idea.
How the work grows
O(amount × #coins) is slow — explodes on big inputs. For each of the `amount` cells you try every coin, so the work is amount × number-of-coins. Brute-forcing every combination of coins is exponential — the table collapses it by reusing each smaller amount's answer. Memory is one row of length amount+1.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.