Interactive Lab · DSA & Algorithms
Dynamic programming scares people, so start with the friendliest version: given coin values, what's the fewest coins that add up to some amount? Grabbing the biggest coin first (greedy) can overpay. Trying every combination (recursion) explodes exponentially. DP threads the needle: solve every smaller amount once, store it in a table, and build each answer from earlier ones, dp[a] = 1 + min over coins c of dp[a−c]. Scrub the fill and watch each cell reach back to the sub-answers it's made of.
🎬 Watch the 80-second explainer, then fill the table yourself below ↓
▶ The playground, pick coins and an amount, then scrub the table filling in
Each cell is dp[a]the fewest coins for amount a. It's built from earlier cells: the arcs point to each dp[a−coin] it could come from, and the green arc is the winning choice. The chip in a cell's corner is the coin it used; ∞ means that amount can't be made.
Coin change is the canonical gateway to dynamic programmingthe technique behind diff tools (edit distance), sequence alignment in genomics, route planning, and resource allocation. The greedy-fails moment you just saw is the interview classic testing whether you know *when* DP is required, not just how.
The code that's actually running, one table, filled once
Set the coins to 1 · 3 · 4 and the amount to 6. Predict greedy first: grab the biggest coin that fits, 4, then 1, then 1, that's 3 coins. Now read the table: dp[6] = 2, because 3 + 3 does it in two. Greedy overpaid, because taking the 4 blocked the perfect pair of 3s. That's the whole reason DP exists: it doesn't commit early, it compares all choices for every sub-amount. Second test: switch to coins 3 · 5 and find an amount that shows ∞why can some totals never be made?
The takeaway
a is one coin c plus the best way to make a − c. The big answer is built from smaller answers, that's what makes DP possible.dp[3] over and over, that's the exponential blow-up you see in the call counter. DP computes each sub-amount once and reuses it: O(amount × coins).dp[] left to right guarantees every dp[a−c] is ready before you need it, no recursion, no stack, just a loop.