Appearance
4.23.8 — Coin Change
LeetCode 322 · Medium · ★ Blind 75
The problem
Given coin denominations and an amount, return the fewest coins that make the amount, or -1 if it cannot be made. You have unlimited coins of each type.
coins = [1,2,5], amount = 11 → 3 (5 + 5 + 1)
coins = [2], amount = 3 → -1Amount up to 10,000.
Why greedy fails
This is the reference example for the DP-versus-greedy question from 4.22, so it is worth having the counterexample ready.
Greedy rule: always take the largest coin that fits.
Counterexample: coins = [1, 3, 4], amount = 6. Greedy takes 4, then 1, then 1 — three coins. The right answer is 3 + 3 — two coins.
Real currencies are deliberately designed so that greedy works, which is exactly why the intuition is so strong and so wrong. When the denominations are arbitrary, greedy is not safe, and one counterexample settles it.
The pattern
Let dp[a] be the fewest coins making amount a.
To make amount a, the last coin you used was some coin c. Before that you had made a − c, using dp[a - c] coins. So:
dp[a] = 1 + \min_{c \,\in\, \text{coins},\ c \le a} dp[a - c]
Read aloud: the cheapest way to make a is one coin, plus the cheapest way to make whatever was left after that coin. Try every coin as the last one and keep the best.
dp[0] = 0 — making zero needs no coins. That is the base case and everything builds from it.
The solution
python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
INF = amount + 1 # bigger than any real answer
dp = [INF] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], 1 + dp[a - c])
return dp[amount] if dp[amount] != INF else -1ts
function coinChange(coins: number[], amount: number): number {
const INF = amount + 1;
const dp = new Array(amount + 1).fill(INF);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);
}
}
return dp[amount] === INF ? -1 : dp[amount];
}INF = amount + 1 rather than infinity. The most coins any reachable amount could need is amount (all 1s), so amount + 1 is unreachable and marks "impossible" without needing floats. It also keeps 1 + dp[...] safe from overflow concerns in typed languages.
The loop order. dp[a] reads dp[a - c], which is always smaller, so the outer loop counts upwards and every cell it needs is already filled.
Coins may be reused freely, and the code allows that automatically: dp[a - c] may itself have used coin c. Compare 4.23.12 Partition Equal Subset Sum, where each item is used once and the loop must run downwards to prevent reuse. That loop direction is the entire difference between the two problems, and it is the trap named in 4.22.
Trace
coins = [1, 2, 5], amount = 6
| a | best option | dp[a] |
|---|---|---|
| 1 | 1 + dp[0] | 1 |
| 2 | 1 + dp[0] via coin 2 | 1 |
| 3 | 1 + dp[1] via coin 2 | 2 |
| 4 | 1 + dp[2] via coin 2 | 2 |
| 5 | 1 + dp[0] via coin 5 | 1 |
| 6 | 1 + dp[5] via coin 1 | 2 |
Two coins for 6: 5 + 1 ✓.
The top-down version
python
from functools import lru_cache
def coinChange(self, coins, amount):
@lru_cache(None)
def fewest(a: int) -> float:
if a == 0: return 0
if a < 0: return float('inf')
return min((1 + fewest(a - c) for c in coins), default=float('inf'))
result = fewest(amount)
return -1 if result == float('inf') else resultEasier to derive, because it is just the recurrence written down. It costs stack depth and hash lookups, and it computes only the amounts actually reachable — which is a genuine advantage when the coins are large and most amounts are unreachable.
Derive with this, ship the table.
Complexity
O(\text{amount} \times \text{number of coins}) time — this is the "states × transitions" formula from 4.22: amount states, and each state tries every coin.
O(\text{amount}) space.
This is pseudo-polynomial, and the distinction is worth knowing. The runtime is polynomial in the value of the amount, not in the number of bits used to write it. Doubling the number of digits in the amount multiplies the work by ten. Coin Change is a cousin of the knapsack problem for exactly this reason, and 4.29 explains why that matters.
Where this goes next
- Coin Change II — count the number of combinations rather than the fewest coins. The loop order flips: coins outside, amounts inside, or you count permutations by accident. That is 4.24.4 and it is one of the most instructive loop-order lessons in the book.
- Combination Sum IV — counts permutations, so the loops go the other way round. Compare the two and the difference becomes obvious.
- Perfect Squares — Coin Change where the coins are 1, 4, 9, 16 and so on.
- Minimum Cost For Tickets — the same shape with three "coins" of different durations.
What the interviewer will push on
"Why not greedy?" [1, 3, 4] and amount 6. Have it ready before they ask.
"What does dp[a] mean?" The fewest coins making exactly a.
"Why dp[0] = 0?" Zero needs no coins, and every other value is built from it.
"How do you mark impossible?" A sentinel larger than any real answer, then convert to -1 at the end.
"Why does the loop go upwards, and when would it go down?" Upwards allows reuse. Downwards prevents it, which is what 0/1 knapsack needs.
"What is the complexity, and is that polynomial?" O(\text{amount} \times \text{coins}), and it is pseudo-polynomial — polynomial in the value, not in the input size.
"How would you return the actual coins?" Store, for each amount, which coin gave the best answer, then walk backwards from amount. Reconstruction needs the table, which is the one thing the O(1)-space tricks give up.
One thing to volunteer: open with the greedy counterexample. It settles the technique choice in ten seconds and shows you tested your first instinct instead of trusting it.
Next: 4.23.9 Maximum Product Subarray — where you have to carry two values because a negative can turn the worst into the best.