Pattern 3: Knapsack (coin change)
"Composing a target by combining items" is one of the most common families of DP — the knapsack family. Coin Change is the perfect representative: forming a value with the fewest number of coins.
Try it first: Coin Change
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Given coins of values coins (an unlimited supply of each) and an amount, return the fewest number of coins that sum to exactly amount, or -1 if it is impossible.
Example: coins = [1,2,5], amount = 11 → 3 (5+5+1).
Tried it? A greedy ("always take the largest coin that fits") fails in some cases (e.g., coins [1,3,4] for 6: greedy gives 4+1+1=3, but 3+3=2 is better). The theory below shows why DP is needed here.
The theory: the target-value table
Define dp[a] = fewest number of coins to form the value a. To compute
dp[a], try using each coin m as the last one: if you use m, the
remainder is a - m, which has already been solved. Take the best among the
options:
dp[a] = min over each coin m (with m <= a) of: dp[a - m] + 1
base cases: dp[0] = 0 (zero coins to form zero)
initialize the rest with "infinity" (impossible)
Since each coin can be used as many times as you want, this is the
unbounded knapsack. Fill dp from 1 up to amount; watch the table take
shape, with the cursor a consulting dp[a - m]:
In the end, dp[amount] is the answer — or -1 if it stayed "infinity"
(impossible to form the value).
Why is it O(amount × coins)?
There are amount + 1 states (dp[0..amount]), and each one tries all the
coins → time O(amount × number of coins), space O(amount). It's the
"states × cost per state" from lesson 1 in action: amount states × O(coins)
each.
Why the greedy fails here (and in the last lesson Jump Game didn't)
In Jump Game, the local choice ("go as far as possible") guaranteed the optimum. In Coin Change, taking the largest coin doesn't guarantee it: sometimes a combination of smaller coins uses fewer pieces. Since the local choice can lead to a dead end, you have to consider all the options and reuse subproblems — exactly what DP does. Recognizing this difference is half the battle.
Variations of the knapsack family
| Problem | State | Recurrence |
|---|---|---|
| Coin Change (min coins) | dp[a] = min coins for a | min(dp[a-m]+1) |
| Combination Sum IV (count) | dp[a] = number of combinations for a | sum of dp[a-m] |
| Partition Equal Subset | dp[v] = can we form v? | dp[v] or dp[v-num] (0/1) |
Notice: Coin Change and Combination Sum IV are almost identical — they just
swap min(...)+1 for sum(...), because one counts the minimum number of
coins and the other how many combinations. The Partition, on the other
hand, is a 0/1 knapsack (each item used at most once), which changes the
direction of the loop. Same skeleton, different questions.
🧠 Review quiz
0/41. In Coin Change, what does dp[a] represent and what is the recurrence?
2. Why is Coin Change an 'unbounded' knapsack?
3. Why does a greedy ('take the largest coin that fits') fail in Coin Change?
4. How do Coin Change (min coins) and Combination Sum IV (count combinations) differ?
Summary
- Knapsack: composing a target from items;
dp[a]indexed by the value. - Coin Change:
dp[a] = min(dp[a-m] + 1)over the coins (unbounded: reusable coins). - O(amount × coins) — states × cost per state.
- Greedy fails (the local choice misleads) ⇒ DP. Combination Sum IV is the same template, counting combinations.
Next lesson: the table gains two dimensions — grid DP.