Overview
Coin change comes in two classic forms. Coin Change I asks for the minimum number of coins to make an amount: dp[a] = 1 + min(dp[a - coin]). Coin Change II asks for the number of combinations that make the amount: dp[a] += dp[a - coin]. Both are unbounded knapsack, because each coin can be used unlimited times.
The subtle point is loop order in the counting version. Coins in the outer loop count combinations (1 + 2 and 2 + 1 are the same). Amounts in the outer loop count ordered sequences (1 + 2 and 2 + 1 are different), which is Combination Sum IV.
To give 11 cents with coins 1, 2, and 5, the cashier asks: if I hand over a 5 first, what is the best way to make the remaining 6? Knowing the best answer for every smaller amount makes each new amount a quick decision.
When to use it
- Make a target from reusable denominations.
- Minimum pieces, steps, or items to reach an exact total.
- Count ways to form a sum when order does or does not matter.
- Perfect squares, stair climbing with arbitrary step sets.
Problem patterns it solves
Recognize it when: fewest items to reach a total.
- 322. Coin Change
- 279. Perfect Squares
- 983. Minimum Cost For Tickets
Recognize it when: number of unordered ways.
- 518. Coin Change II
- Ways to make change
Recognize it when: number of ordered ways; different orders count separately.
- 377. Combination Sum IV
- 70. Climbing Stairs (steps as coins)
- 1155. Number of Dice Rolls With Target Sum
Recognize it when: canonical coin systems where greedy works (1, 5, 10, 25).
- 860. Lemonade Change
- 2144. Minimum Cost of Buying Candies With Discount
Where it is used in real software
Dispensing change with the fewest coins or notes, respecting available inventory.
Fulfilling an order quantity using pack sizes (6-packs, 12-packs) with the fewest packages.
Meeting a capacity target with a combination of instance sizes at minimum count or cost.
Key terms
- dp[a] (min version)
- Fewest coins that sum to amount a; Infinity if impossible.
- dp[a] (count version)
- Number of ways to make amount a.
- Unbounded
- Each coin can be reused, so the capacity loop goes upward.
- Canonical coin system
- A coin set where the greedy largest-coin-first rule is always optimal.
How it works, step by step
- 1Min coins: initialize
dp[0] = 0, dp[1..amount] = Infinity.
- 2Min coins: transition
For each amount a and coin c <= a: dp[a] = min(dp[a], dp[a - c] + 1).
- 3Count combinations: initialize
dp[0] = 1 (one way to make zero: take nothing).
- 4Count combinations: coins outer, amounts inner
for coin: for a from coin to amount: dp[a] += dp[a - coin].
- 5Return
Min version: dp[amount] or -1 if Infinity. Count version: dp[amount].
STEP 1dp[0] = 0: zero coins make amount 0.
Coin Change II: combinations for amount 5 with coins [1, 2, 5]
dp[a] after processing each coin (coins in the outer loop)
| After coin | a=0 | a=1 | a=2 | a=3 | a=4 | a=5 |
|---|---|---|---|---|---|---|
| start | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 3 | 3 |
| 5 | 1 | 1 | 2 | 2 | 3 | 4 |
NOWAfter coin: start | a=0: 1 | a=1: 0 | a=2: 0 | a=3: 0 | a=4: 0 | a=5: 0
4 combinations: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1. Because coins are introduced one at a time, each combination is counted once in coin order.
Implementation
function coinChange(coins, amount) { const dp = new Array(amount + 1).fill(Infinity); dp[0] = 0; for (let a = 1; a <= amount; a++) { for (const c of coins) { if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1; } } return dp[amount] === Infinity ? -1 : dp[amount];} // 518. Coin Change II: combinations (coins outer)function change(amount, coins) { const dp = new Array(amount + 1).fill(0); dp[0] = 1; for (const c of coins) { for (let a = c; a <= amount; a++) dp[a] += dp[a - c]; } return dp[amount];} // 377. Combination Sum IV: ordered sequences (amount outer)function combinationSum4(nums, target) { const dp = new Array(target + 1).fill(0); dp[0] = 1; for (let a = 1; a <= target; a++) { for (const x of nums) if (x <= a) dp[a] += dp[a - x]; } return dp[target];} // 279. Perfect Squares: coins are 1, 4, 9, 16, ...function numSquares(n) { const dp = new Array(n + 1).fill(Infinity); dp[0] = 0; for (let a = 1; a <= n; a++) { for (let s = 1; s * s <= a; s++) dp[a] = Math.min(dp[a], dp[a - s * s] + 1); } return dp[n];}Complexity and performance
Each amount tries each coin.
One dp array.
sqrt(n) square 'coins'.
Trade-offs
Greedy (largest coin first) works for canonical systems like US coins but fails for coins [1, 3, 4] and amount 6 (greedy 3 coins, optimal 2).
BFS over amounts also finds the minimum and can stop early, but uses a queue; DP is simpler and handles counting too.
Variants and related techniques
Bounded knapsack: iterate downward per copy or split counts into powers of two.
Store the last coin used for each amount and walk back.
Counts can be huge; problems often ask modulo 10^9 + 7.
Common mistakes
- Using greedy for arbitrary coin sets.
Fix: Use DP unless the coin system is known to be canonical.
- Wrong loop order for counting.
Fix: Coins outer = combinations; amount outer = permutations (ordered sequences).
- Integer.MAX_VALUE + 1 overflow in Java.
Fix: Initialize with amount + 1 as infinity.
Interview questions
Why does loop order change the count?
With coins outer, each coin is introduced once and combinations are built in a fixed coin order, so each set is counted once. With amounts outer, every coin can be the last one at every step, so different orders are counted separately.
Why doesn't greedy always work?
Taking the largest coin can leave a remainder that needs many small coins. With coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 while 3 + 3 is optimal.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| 322. Coin Change | Medium | Minimum coins. |
| 518. Coin Change II | Medium | Combinations. |
| 377. Combination Sum IV | Medium | Ordered sequences. |
| 279. Perfect Squares | Medium | Squares as coins. |
| 1155. Number of Dice Rolls With Target Sum | Medium | Bounded rounds. |