Coin Change
Fewest coins for amount = 1 + the best over amount minus each coin.
Interactive DP Fill
Problem
Given a collection of coin denominations and a target amount, determine the minimum number of coins needed to total that amount. You may use each denomination any number of times. Return -1 when no combination of the available coins can form the target.
Examples
Input: coins = [1, 3, 4], amount = 6
Output: 2
Input: coins = [2], amount = 3
Output: -1
The Goal
Find the fewest coins that add up to amount. You can use each coin as often as you like. If no mix of coins works, return -1.
For coins = [1, 3, 4] and amount = 6, the answer is 2: 3 + 3. Taking the 4 first gives 4 + 1 + 1, which is three coins.
Minimize the coin count
Reaching the amount isn't enough. 4 + 1 + 1 makes 6 too, but 3 + 3 does it with one coin fewer.
The Recurrence
Take the best way to make amount a and look at its last coin. What's left, a - coin, must also be made with the fewest coins. So try every coin that fits and keep the smallest:
dp[a] = min(dp[a], 1 + dp[a - coin])
Start with dp[0] = 0 and every other amount at ∞. The code stores ∞ as amount + 1, more coins than any answer uses.
Make coin the last coin, and add 1 to the best for what's left.
For 6, coin 3 gives 1 + dp[3] = 2.
The Algorithm
Every coin is positive, so dp[a] only reads smaller amounts. Fill the table left to right and those are always ready.
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
dp[a] = min(dp[a], 1 + dp[a - coin])Return dp[amount], or -1 if it's still ∞. With amount = 6, the table goes from [0, ∞, ∞, ∞, ∞, ∞, ∞] to [0, 1, 2, 1, 1, 2, 2].
| Method | Rule | Result | Memory |
|---|---|---|---|
| Bottom-up DP | Try every coin at every amount | Always optimal | O(amount) |
| Greedy | Take the largest coin that fits | Can fail | O(1) |
| Brute force | Try every combination | Optimal but slow | O(amount) recursion depth |
Walkthrough
Run it with coins = [1, 3, 4] and amount = 6. Each amount tries all three coins and keeps the fewest.
Amounts 3 and 4 take one coin each, and 5 takes two. At 6, coin 1 gives 1 + dp[5] = 3, coin 3 gives 1 + dp[3] = 2, and coin 4 gives 1 + dp[2] = 3. So dp[6] = 2.
The best answer for 6 is built from the best answer for 3.
Checkpoint · predict the next step
Step 3 of 8 on the stage: Amount 2: coin 1 gives 1 + dp[1] = 2; coin 3 is too big; coin 4 is too big. The fewest is 2, so dp[2] = 2.
dp = [0, 1, 2, ∞, ∞, ∞, ∞]
Pitfalls
- Greedy fails here. It takes the 4, then needs
1 + 1: three coins against two. - Skip coins bigger than
a, ora - coingoes negative. - Never return the ∞ stand-in. Coins
[2]can't make 3, sodp[3]stays ∞ and the answer is -1. amount = 0needs no coins, anddp[0] = 0already says so.
For coins [1, 3, 4] and amount 6, why does largest-coin-first fail?
Complexity
Every amount from 1 to amount tries every coin, so time is O(amount · coins), where coins is how many kinds there are. The table holds one entry per amount, so space is O(amount).
For 6 and three coins, that's at most 18 checks.
Fill the table once
- Create dpOne entry per amount, 0 through the target.O(amount)
- Try each coin at each amountThis nested loop dominates.O(amount · coins)
- Read the answerdp[amount] is already there.O(1)
Each amount is solved once and reused.
In short
Build dp[0..amount] where dp[a] is the minimum coins to make a. For each amount, try every coin and take 1 + dp[a − coin], seeding dp[0] = 0 and everything else as infinity. The final dp[amount] is the answer, or −1 if unreachable.
Common mistake
Using a greedy largest-coin-first approach — it fails for coin systems like [1, 3, 4] making 6.