Unbounded knapsack (coin change)
Sweep capacities upward so an item can be reused.
dp[a] is the best for amount a using any number of each coin.
01The intuition
Start with what you would do by hand
Coins of 1, 2 and 5 rupees, unlimited of each. What is the fewest coins that make 11? By hand you reach for the biggest first: 5 + 5 + 1, three coins. That greedy habit works for these coins, but try coins of 1, 3 and 4 making 6: greedy gives 4 + 1 + 1, three coins, while 3 + 3 is two. So "biggest first" is not reliable, and the honest by-hand method is to consider every way, which blows up quickly.
Build the structure, one piece at a time
Piece one: a row dp[0] to dp[11], where dp[a] will be the fewest coins making amount a. dp[0] = 0, because zero rupees needs zero coins. Everything else starts as "unknown", written ∞.
Piece two: the thought for one amount. Whatever the best pile for 11 is, it has a last coin, which is 1, 2 or 5. Remove it and you are left with a best pile for 10, 9 or 6. So
dp[a] = 1 + min( dp[a − 1], dp[a − 2], dp[a − 5] ) over coins that fit
Piece three, the rule that allows reuse: sweep amounts upward, 1, 2, 3, ... This is the opposite of the 0/1 knapsack sweep. Going upward, dp[a − coin] already includes piles that use the same coin, so a coin may appear many times, which is exactly what we want.
| amount | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| dp | 0 | 1 | 1 | 2 | 2 | 1 | 2 | 2 | 3 | 3 | 2 | 3 |
Check dp[3]: 1 + min(dp[2], dp[1]) = 1 + 1 = 2, the pile 2 + 1. Check dp[11]: 1 + min(dp[10], dp[9], dp[6]) = 1 + 2 = 3, the pile 5 + 5 + 1. For the 1, 3, 4 coins and amount 6 the same table gives dp[6] = 1 + min(dp[5], dp[3], dp[2]) = 1 + 1 = 2, fixing the greedy mistake.
Why it is correct
The invariant: when dp[a] is written, it is the true minimum for amount a. It holds for 0. For larger a, any pile for a ends with some coin c and the rest is a pile for a − c, which cannot beat dp[a − c]; the formula takes the best over every possible last coin, so it is neither too large nor too small. The upward order guarantees every dp[a − c] is final before it is read.
Why it is fast
Each amount tries each coin once:
work = (number of coins) × amount, 33 steps here, 300,000 for 30 coins and amount 10,000
How to recognise it in an interview
Cues: "unlimited supply", "may reuse", "fewest coins", "number of ways to make the amount", "sum of perfect squares". The first thing to say: "a row over amounts swept upward so items repeat." Coin Change is the example above. Coin Change II counts ways instead of minimising: loop over coins on the outside and amounts on the inside, adding dp[a − c] into dp[a], so each combination is counted in one coin order. Perfect Squares is this with the coins being 1, 4, 9, 16, and so on.
02The idea in one line
Sweep capacities upward so an item can be reused.
Reach for it when: Coin change (min), coin change II (ways), perfect squares, combination sum IV.
Cost: O(n · amount) time.
03The walk-through, step by step
The video works one example: Coin Change coins [1,2,5] amount 11. These are its captions in order, so you can follow without the video or check a step you missed.
- Sweep amounts upward: dp[a] = 1 + min(dp[a − coin]) over coins that fit
- dp[1] = 1 + min(dp[0]) = 1
- dp[2] = 1 + min(dp[1], dp[0]) = 1
- dp[3] = 1 + min(dp[2], dp[1]) = 2
- dp[4] = 1 + min(dp[3], dp[2]) = 2
- dp[5] = 1 + min(dp[4], dp[3], dp[0]) = 1
- dp[6] = 1 + min(dp[5], dp[4], dp[1]) = 2
- dp[7] = 1 + min(dp[6], dp[5], dp[2]) = 2
- dp[8] = 1 + min(dp[7], dp[6], dp[3]) = 3
- dp[9] = 1 + min(dp[8], dp[7], dp[4]) = 3
- dp[10] = 1 + min(dp[9], dp[8], dp[5]) = 2
- dp[11] = 1 + min(dp[10], dp[9], dp[6]) = 3
- dp[11] = 3: 5 + 5 + 1
- Upward sweep lets a coin repeat: O(coins · amount)
04Asked at Google
7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Coin Change | Medium | 48 | last 6 months |
| Perfect Squares | Medium | 39 | last 6 months |
| Coin Change II | Medium | 38 | last 6 months |
| Combination Sum IV | Medium | 33 | last 6 months |
| Integer Break | Medium | 20 | last 6 months |
| Number of Dice Rolls With Target Sum | Medium | 20 | last 6 months |
| Minimum Cost For Tickets | Medium | 17 | last 6 months |
05Related patterns
Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).