Coin Change
The problem: you have unlimited coins of a few denominations — here 1, 3, 4 — and a target amount. What is the fewest coins that make the target exactly?
These coins are chosen to punish the obvious idea. Reach for the biggest coin that fits and you will make 6 in three coins; it can be done in two. You will find that out yourself in beat 1, and it is the reason the remaining five beats exist.
Play the game
Make exactly 6 from coins 1, 3, 4 — using as few coins as you can.
Make exactly 6
6 to go
This purse: empty
Discover the rule
One bucket per coin. The bucket count was never fixed at two.
Only the last coin matters
Take any purse that makes 6 and lay the coins in a row. Whatever coin you put last, the coins before it must make 6 minus that coin. So every purse belongs to one bucket per coin — and there are only 3 coins.
3 + 3 = 6Spend 1 last
The rest must make 5, which takes 2 coins.
Spend 3 last
The rest must make 3, which takes 1 coin.
Spend 4 last
The rest must make 2, which takes 2 coins.
Finish beat 1 to unlock
Follow recursion
Three branches per call instead of two. Watch how much faster it rots.
Recurrence
The rule says what an answer depends on:
coin(a) = 1 + min over c of coin(a - c)Recursion
The code follows that rule by calling itself once per coin that fits, until it reaches coin(0) — the only amount whose answer is free.
function fewest(a, coins) {
if (a === 0) return 0;
let best = Infinity;
for (const c of coins) {
if (c <= a) best = Math.min(best, fewest(a - c, coins) + 1);
}
return best;
}Run the recursive code for coin(6). Tap a yellow call to reveal the calls it makes. Keep going until the tree is complete.
1 / 24 callsFinish beat 2 to unlock
Add memory
Decide when the cache already knows the answer.
Same recursion, one new ingredient
Recursion still starts at coin(7) and asks about smaller amounts. This time it carries a cache, so each amount can be answered once and remembered.
Current call stack
coin(7)coin(6)coin(5)coin(4)coin(3)coin(2)Top-down means we began with coin(7) and followed its smaller dependencies.
Cache
The base cases start filled because their answers are already defined.
Decision 1 of 3
Recursion requests coin(2). What should it do?
Finish beat 3 to unlock
Build bottom-up
Fill every amount in order, and confirm the number you predicted.
New task: build the same answers without recursive calls
Memoization is top-down
Start at 7, recurse down toward 0, and save each amount as it resolves.
Tabulation is bottom-up
Start at 0 and fill each amount once every amount it depends on already exists.
Both store the same meaning: the fewest coins that make exactly a. Only the order changes.
Press start. The animation stops at every cell YOUR recurrence must fill.
Before you fill: one starting fact
Given base casedp[0] = 0Making zero takes no coins. Every other answer is some number of coins stacked on top of this one.
Only one base case this time, and it is doing a lot of work: it is what stops 1 + min(...) from recursing forever.
- 1
function coinChange(coins, amount) { - 2
const dp = [0]; - 3
for (let a = 1; a <= amount; a++) { - 4
dp[a] = Infinity; - 5
for (const c of coins) { - 6
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1); - 7
} - 8
} - 9
return dp[amount]; - 10
}
Finish beat 4 to unlock
Make it transfer
Counting combinations, one coin of each, and why greedy fails.
Variation 1: instead of the fewest coins, count how many distinct COMBINATIONS make the amount. What changes?
Variation 2: you now have exactly ONE coin of each denomination. What breaks in dp[a] = 1 + min(dp[a - c])?
Variation 3: does sorting the coins descending and always taking the largest that fits ever fail?
Final check: house robber always had two buckets. Coin change has one per coin. What determines the number of buckets?
Finish beat 5 to unlock
The pattern, formally
The state: dp[a] is the fewest coins that sum to exactly a. The recurrence: whichever coin c you spend last, the rest must make a - c. So dp[a] = 1 + min(dp[a - c]) over every coin that fits, with dp[0] = 0. Amounts no combination reaches stay at ∞, which is why ∞ is the right initial value rather than 0 or −1: it composes with min without a special case. Time is O(amount × coins), space O(amount).
Naive recursion
Branch once per coin, all the way down. Nothing is stored.
O(coinsᵃᵐᵒᵘⁿᵗ) time
O(amount) call stack
Memoization
Same branching, but each amount resolves once and is cached.
O(amount × coins) time
O(amount) cache plus stack
Tabulation
Sweep amounts upward, taking a min over the coins each time.
O(amount × coins) time
O(amount) table
Takeaways
- The number of buckets equals the number of possible last decisions. Two step sizes gave two; three coins give three. Nothing was ever special about two.
- Greedy fails here and the failure is instructive: committing to the largest coin discards options the comparison had not made yet.
- Infinity is the honest value for an unreachable amount. It composes with min, so no branch of the code needs a special case for impossible.
- The +1 in dp[a] = 1 + min(dp[a - c]) is the coin you spend. The min is the choice of which coin that is.
- Coins can repeat because the state only tracks the amount. The moment you have one coin of each, the state is incomplete and needs a second dimension.
- Counting combinations instead of minimizing coins keeps the same states but changes the combine step to a sum — and needs the coin loop outside to avoid counting permutations.