Coin Change —
The minimum-coins DP table, filled amount by amount.
Given coin denominations and a target amount, find the fewest coins needed to make that amount exactly. Build a DP array where each cell answers "the minimum coins for this amount" using every coin denomination that could have been used last. Watch the table fill from 0 up to the target on LearnBug and see each coin's contribution to each cell.
What is the Coin Change problem?
Given coins like [1, 2, 5] and a target amount, find the minimum number of coins that sum to exactly that amount (unlimited supply of each coin). For every amount a, the answer is 1 + min(dp[a - coin]) across every coin that's ≤ a — try using each coin last, and take whichever choice needed the fewest coins before it.
Why visualization helps
Each cell in the DP array depends on multiple earlier cells — one per coin denomination — which is more than the single-predecessor pattern in Climbing Stairs. LearnBug highlights which specific coin produced the winning minimum at each amount, so the "try every coin, keep the best" logic is visibly happening, not just implied by the formula.
The trap this problem is designed to expose
Greedy fails on some coin sets
With coins [1, 3, 4] and amount 6, greedy picks 4 then 1+1 (3 coins), but the real minimum is 3+3 (2 coins) — greedy's "biggest coin first" logic isn't always optimal.
DP checks every possibility, correctly
By computing the true minimum for every smaller amount first, DP guarantees the optimal answer for every amount — no risk of a locally-good choice turning out globally wrong.
"Unbounded" — coins can repeat
Unlike 0/1 Knapsack, each coin denomination can be used as many times as needed — that's why the DP loop doesn't need to track "used" state per coin.
coin_change([1, 2, 5], 11) — a partial trace
dp[0] = 0 (zero coins for zero amount). dp[1] through dp[4] fill in using coins 1 and 2
dp[1]=1 (one 1-coin). dp[2]=1 (one 2-coin, beats two 1-coins). dp[3]=2 (2+1). dp[4]=2 (2+2, beats 1+1+1+1).
dp[5]: try coin 1 (dp[4]+1=3), coin 2 (dp[3]+1=3), coin 5 (dp[0]+1=1) — take the minimum
This is the first amount where the 5-coin becomes usable. Using one 5-coin directly (dp[0]+1=1) beats both other options by a wide margin.
dp[6] through dp[10] continue the same three-way comparison at every amount
dp[6] = dp[5]+1 = 2 (one 5, one 1). dp[10] = dp[5]+1... but also dp[8]+2 via the 2-coin — every amount checks all three coins and keeps the best.
dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = min(3, 4, 3) = 3
Via coin 1: dp[10]+1 = 3. Via coin 2: dp[9]+1 = 4. Via coin 5: dp[6]+1 = 3. Two options tie at 3 — either works (e.g. 5+5+1, or 5+2+2+2 uses 4, so it's really 5+5+1).
Return: dp[11] = 3 ✓ minimum 3 coins (5 + 5 + 1) to make 11
Bottom-up minimum coins
def coin_change(coins, amount):
dp = [float("inf")] * (amount + 1)
dp[0] = 0 # 0 coins needed to make amount 0
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
dp[a] = min(dp[a], dp[a - coin] + 1) # try using this coin last
return dp[amount] if dp[amount] != float("inf") else -1
print(coin_change([1, 2, 5], 11)) # 3Complexity Notes
Frequently asked questions
Why doesn't a greedy "always use the biggest coin" approach work?
It works for some coin systems (like standard currency — 1, 5, 10, 25) but not all. With coins [1, 3, 4] and amount 6, greedy picks 4 first, leaving 2, which needs two 1-coins — 3 coins total. The true optimum is 3+3, just 2 coins. DP avoids this failure entirely because it checks every possible last coin, not just the largest one.
Why initialize the array with float("inf") instead of 0?
Infinity represents "not yet known to be reachable" — using min() against it means any real coin combination will always be smaller and win. If 0 were used instead, every min() comparison would incorrectly treat unreached amounts as already solved with zero coins.
What does "unbounded" mean in this context?
It means each coin denomination can be used any number of times — no limit on how many 1-coins, 2-coins, or 5-coins you use. This is why the inner loop just checks dp[a - coin] for the current amount being built, rather than tracking which specific coins have already been "spent," as a 0/1 (limited-supply) version would need to.
How is this different from asking "how many ways can I make this amount?"
That's a related but different problem — counting combinations instead of minimizing coins. It uses a similar DP table but with dp[a] += dp[a - coin] (summing possibilities) instead of dp[a] = min(dp[a], dp[a-coin]+1) (minimizing count), and the loop order (coins outside, amounts inside) actually matters there to avoid counting the same combination multiple times in a different order.
Watch the minimum-coins table fill in, amount by amount
Paste coin change into LearnBug and see which coin wins at every amount.