Builds on Linear DP, which you haven’t finished yet.
Unbounded Knapsack (Coin Change, Coin Change II)
Coin Change (LC 322)(opens leetcode.com)
You're given an array coins of coin denominations, each reusable as many times as you like, and a target amount of money.
Work out the smallest number of coins whose values add up to exactly amount, or return -1 if no combination of the given coins reaches that amount exactly.
Unbounded Knapsack
items & capacities ➔ capacity loop runs upward so an item can repeat ➔ dp[w]| 1 | def coin_change(coins: list[int], amount: int) -> int: |
| 2 | """Unbounded Knapsack: the fewest coins that make amount, each coin usable any number of times (forward loop). |
| 3 | Time: O(N * amount) | Space: O(amount) |
| 4 | """ |
| 5 | # dp: dp[w] is the fewest coins that make amount w; infinity marks w as not yet reachable |
| 6 | dp = [float('inf')] * (amount + 1) |
| 7 | dp[0] = 0 |
| 8 | for coin in coins: |
| 9 | for w in range(coin, amount + 1): |
| 10 | # 1. Reuse This Coin Forward: |
| 11 | # The forward loop lets dp[w - coin] already include this coin, so one coin may be used any number of times. |
| 12 | dp[w] = min(dp[w], dp[w - coin] + 1) |
| 13 | return int(dp[amount]) if dp[amount] != float('inf') else -1 |
dp[w] is the fewest coins that make w using only the coins processed so far, each any number of times.Treat each amount as its own subproblem: dp[w] is the fewest coins that make w, and each coin updates it from dp[w - coin]. Loop w upward, so dp[w - coin] may already include this coin and the coin can repeat. Start from infinity, which marks an amount as not yet reachable, and only dp[0] = 0. The trap is the loop direction: for w in range(coin, amount + 1), not downward, which would use each coin at most once.
See it run
Coin Change, step by step
coin -w -dp[amount] inf
Row k is the list dp after the k-th coin. Column w is the amount w.
writethe cell being writtenreadthe cell dp[w - coin], which may already include this coinanswerthe final answer
Start: coins = [1, 2, 5] and amount = 11. dp[0] = 0 because the amount 0 needs no coin. Every other cell is inf, which means the amount cannot be made yet.
Gotcha 1 of 3
- The trap
Gotcha 1: Looping
wdownward when items can be reusedMistakefor w in range(amount, coin - 1, -1):Fixfor w in range(coin, amount + 1):What happens: Going upward,
dp[w - coin]may already include thiscoin, sodp[w]can use it again. That is what 'any number of times' needs. Going downward readsdp[w - coin]before this pass updates it, so each coin is used at most once, which is the 0/1 rule. Withcoins = [2], amount 4 needs the coin twice.Example: coins = [2], amount = 4Mistake: returns -1Fix: returns 2
- Each item can be used at most once, as in Partition Equal Subset Sum (LC 416): the capacity loop runs downward, so an item cannot fill
dp[w - item]and thendp[w]in the same pass. See 0/1 Knapsack - You must return every combination itself, not just the best value or the number of ways, as in Combination Sum (LC 39): a table of numbers per amount can't list them. See Combinations
Deep Dive
The state is an amount, and each item may repeat
In an unbounded knapsack problem, each item can be used any number of times. In Coin Change (LC 322), the state is an amount w, and dp[w] is the fewest coins that make w using only the coins processed so far.
The answer type changes with the problem. In coin_change, dp[w] is a minimum. In Coin Change II (LC 518), it is a number of ways. In Perfect Squares (LC 279), the items are the squares 1, 4, 9 and so on, and dp[w] is the fewest squares that add up to w.
After coin k, dp describes the first k coins, each used any number of times. The next coin adds the choice: end with this coin, so dp[w] can become dp[w - coin] + 1.
Example: for coins = [1, 2, 5] and amount 11, the answer is 3, namely 5 + 5 + 1. After the coin 1, dp is [0, 1, 2, ..., 11]. After the coin 2, dp[11] is 6. After the coin 5, dp[11] is 3.
Why the forward loop lets a coin repeat
The inner loop runs w upward from coin. When the loop updates dp[w], the smaller index w - coin was already updated in this pass. So dp[w - coin] may already include this coin, and dp[w] can use it again.
This is exactly what 'any number of times' needs. For coins = [2] and amount 4, dp[2] becomes 1, and then dp[4] reads dp[2] and becomes 2. The answer is 2.
A downward loop would read dp[w - coin] before it is updated, so each coin would be used at most once. That is the rule of 0/1 Knapsack. With a downward loop, coin_change([2], 4) returns -1 instead of 2.
Infinity or 0 for the unreachable start
In a minimum problem, an amount that cannot be made yet must lose every comparison. So dp starts as infinity, and only dp[0] = 0 is real. Infinity marks an amount as not reachable yet.
With 0 everywhere, min keeps 0 for every amount, and an amount that cannot be made looks free. coin_change([2], 3) would return 0 instead of -1.
At the end, the code returns -1 when dp[amount] is still infinity. A counting problem uses a different start: dp[0] = 1, the one way to make 0 with no coin, and 0 for the others.
Which loop is outer when you count
For a minimum, the order of the two loops does not change the result. For a count, it does.
With coins in the outer loop, as in coin_change, each combination is built in the order of the coin list, so it is counted once. This is Coin Change II (LC 518): for amount 3 and coins [1, 2], the answer is 2, namely 1 + 1 + 1 and 1 + 2.
With amounts in the outer loop, 1 + 2 and 2 + 1 are different sequences, and both are counted. This is Combination Sum IV (LC 377), which counts ordered sequences. For nums = [1, 2, 3] and target 4 the answer is 7. The same loop on Coin Change II (LC 518) gives 3 for amount 3, which is wrong there.
The cost is O(N * amount) time and O(amount) space, where N is the number of coins. Like 0/1 Knapsack, this depends on the value of amount, so check that it is small.
60-Second Pitch
"The brute force tries every sequence of coins, which grows exponentially with the amount. I define dp[w] as the fewest coins that make the amount w. Only dp[0] = 0 is real, and every other amount starts at infinity, which means not reachable yet. For each coin, I loop w upward and set dp[w] to the smaller of its value and dp[w - coin] + 1. The upward loop lets dp[w - coin] already include this coin, so a coin can repeat. There are N coins and the amount as the number of sums, so the time is O(N * amount) and the space is O(amount). If the problem asks for the number of ways, I start with dp[0] = 1 and keep the coins in the outer loop, so each combination is counted once."
Common Questions
- Why does the forward loop allow a coin to repeat?
When the loop reaches
dp[w], the smaller indexw - coinwas already updated in this pass, so it may already include the coin. Using it again adds one more copy of the same coin. A downward loop reads the old value, so each coin is used at most once.- Does the order of the two loops matter?
- What are the time and space complexity?
O(N * amount) time and O(amount) space, where
Nis the number of coins. It is pseudo-polynomial, because it grows with the value of the amount, not with its number of digits.- Why not take the largest coin first?
A greedy choice is wrong for some coin sets. With coins
[1, 3, 4]and amount 6, greedy picks 4 + 1 + 1, which is 3 coins, and the best is 3 + 3, which is 2 coins. The table checks every coin for every amount, so it does not make that mistake.- How does Perfect Squares (LC 279) use this?
The items are the squares 1, 4, 9 and so on up to
n, each usable any number of times, and the goal is the fewest items that add up ton. It iscoin_changewith those squares as the coins. Forn = 12the answer is 3, namely 4 + 4 + 4. Forn = 13it is 2, namely 4 + 9.
SWE Reasoning
Spot it
- You build a target amount from items, and each item can be used any number of times: coins, squares, step sizes.
- The question asks for the fewest items, or for the number of ways to reach the amount.
- The amount is small enough to be an array index.
- The statement says whether the order of the items matters. If it does not, count combinations. If it does, count sequences.
- A greedy choice of the largest coin fails on some coin sets, so a table is needed. With coins
[1, 3, 4]and amount 6, the best answer is 3 + 3, and greedy gives 4 + 1 + 1.
The invariant, step by step
dpstarts as infinity for every amount, anddp[0] = 0. Only the amount 0 is reachable before any coin.- The outer loop takes one coin. At this moment
dp[w]is correct for all coins before it. - The inner loop visits each amount
wfromcoinup toamount. - The update
dp[w] = min(dp[w], dp[w - coin] + 1)readsdp[w - coin], which this pass may already have updated. So the coin can be used again. - When the outer loop ends,
dp[w]is the fewest coins that makewwith all coins, each any number of times, which is the card's invariant. - The code returns
dp[amount], or -1 if it is still infinity.
Traps
- Loop downward when items can repeat. Each coin is used at most once.
coin_change([2], 4)returns -1 instead of 2. - Put the amounts in the outer loop to count combinations. Each order is counted separately. For Coin Change II (LC 518) with amount 3 and coins
[1, 2]the result is 3 instead of 2. - Fill
dpwith 0 instead of infinity in a minimum problem. Every amount looks reachable with 0 coins.coin_change([2], 3)returns 0 instead of -1. - Forget the -1 at the end. If
dp[amount]is still infinity, returning it as a number gives a wrong or invalid answer. - Use a greedy choice. Taking the largest coin first fails for
coins = [1, 3, 4]and amount 6.
Practice
Builds on Linear DP, which you haven’t finished yet.
Unbounded Knapsack (Coin Change, Coin Change II)
Coin Change (LC 322)(opens leetcode.com)
You're given an array coins of coin denominations, each reusable as many times as you like, and a target amount of money.
Work out the smallest number of coins whose values add up to exactly amount, or return -1 if no combination of the given coins reaches that amount exactly.
Unbounded Knapsack
items & capacities ➔ capacity loop runs upward so an item can repeat ➔ dp[w]| 1 | def coin_change(coins: list[int], amount: int) -> int: |
| 2 | """Unbounded Knapsack: the fewest coins that make amount, each coin usable any number of times (forward loop). |
| 3 | Time: O(N * amount) | Space: O(amount) |
| 4 | """ |
| 5 | # dp: dp[w] is the fewest coins that make amount w; infinity marks w as not yet reachable |
| 6 | dp = [float('inf')] * (amount + 1) |
| 7 | dp[0] = 0 |
| 8 | for coin in coins: |
| 9 | for w in range(coin, amount + 1): |
| 10 | # 1. Reuse This Coin Forward: |
| 11 | # The forward loop lets dp[w - coin] already include this coin, so one coin may be used any number of times. |
| 12 | dp[w] = min(dp[w], dp[w - coin] + 1) |
| 13 | return int(dp[amount]) if dp[amount] != float('inf') else -1 |
dp[w] is the fewest coins that make w using only the coins processed so far, each any number of times.Treat each amount as its own subproblem: dp[w] is the fewest coins that make w, and each coin updates it from dp[w - coin]. Loop w upward, so dp[w - coin] may already include this coin and the coin can repeat. Start from infinity, which marks an amount as not yet reachable, and only dp[0] = 0. The trap is the loop direction: for w in range(coin, amount + 1), not downward, which would use each coin at most once.
See it run
Coin Change, step by step
coin -w -dp[amount] inf
Row k is the list dp after the k-th coin. Column w is the amount w.
writethe cell being writtenreadthe cell dp[w - coin], which may already include this coinanswerthe final answer
Start: coins = [1, 2, 5] and amount = 11. dp[0] = 0 because the amount 0 needs no coin. Every other cell is inf, which means the amount cannot be made yet.
Gotcha 1 of 3
- The trap
Gotcha 1: Looping
wdownward when items can be reusedMistakefor w in range(amount, coin - 1, -1):Fixfor w in range(coin, amount + 1):What happens: Going upward,
dp[w - coin]may already include thiscoin, sodp[w]can use it again. That is what 'any number of times' needs. Going downward readsdp[w - coin]before this pass updates it, so each coin is used at most once, which is the 0/1 rule. Withcoins = [2], amount 4 needs the coin twice.Example: coins = [2], amount = 4Mistake: returns -1Fix: returns 2
- Each item can be used at most once, as in Partition Equal Subset Sum (LC 416): the capacity loop runs downward, so an item cannot fill
dp[w - item]and thendp[w]in the same pass. See 0/1 Knapsack - You must return every combination itself, not just the best value or the number of ways, as in Combination Sum (LC 39): a table of numbers per amount can't list them. See Combinations
Deep Dive
The state is an amount, and each item may repeat
In an unbounded knapsack problem, each item can be used any number of times. In Coin Change (LC 322), the state is an amount w, and dp[w] is the fewest coins that make w using only the coins processed so far.
The answer type changes with the problem. In coin_change, dp[w] is a minimum. In Coin Change II (LC 518), it is a number of ways. In Perfect Squares (LC 279), the items are the squares 1, 4, 9 and so on, and dp[w] is the fewest squares that add up to w.
After coin k, dp describes the first k coins, each used any number of times. The next coin adds the choice: end with this coin, so dp[w] can become dp[w - coin] + 1.
Example: for coins = [1, 2, 5] and amount 11, the answer is 3, namely 5 + 5 + 1. After the coin 1, dp is [0, 1, 2, ..., 11]. After the coin 2, dp[11] is 6. After the coin 5, dp[11] is 3.
Why the forward loop lets a coin repeat
The inner loop runs w upward from coin. When the loop updates dp[w], the smaller index w - coin was already updated in this pass. So dp[w - coin] may already include this coin, and dp[w] can use it again.
This is exactly what 'any number of times' needs. For coins = [2] and amount 4, dp[2] becomes 1, and then dp[4] reads dp[2] and becomes 2. The answer is 2.
A downward loop would read dp[w - coin] before it is updated, so each coin would be used at most once. That is the rule of 0/1 Knapsack. With a downward loop, coin_change([2], 4) returns -1 instead of 2.
Infinity or 0 for the unreachable start
In a minimum problem, an amount that cannot be made yet must lose every comparison. So dp starts as infinity, and only dp[0] = 0 is real. Infinity marks an amount as not reachable yet.
With 0 everywhere, min keeps 0 for every amount, and an amount that cannot be made looks free. coin_change([2], 3) would return 0 instead of -1.
At the end, the code returns -1 when dp[amount] is still infinity. A counting problem uses a different start: dp[0] = 1, the one way to make 0 with no coin, and 0 for the others.
Which loop is outer when you count
For a minimum, the order of the two loops does not change the result. For a count, it does.
With coins in the outer loop, as in coin_change, each combination is built in the order of the coin list, so it is counted once. This is Coin Change II (LC 518): for amount 3 and coins [1, 2], the answer is 2, namely 1 + 1 + 1 and 1 + 2.
With amounts in the outer loop, 1 + 2 and 2 + 1 are different sequences, and both are counted. This is Combination Sum IV (LC 377), which counts ordered sequences. For nums = [1, 2, 3] and target 4 the answer is 7. The same loop on Coin Change II (LC 518) gives 3 for amount 3, which is wrong there.
The cost is O(N * amount) time and O(amount) space, where N is the number of coins. Like 0/1 Knapsack, this depends on the value of amount, so check that it is small.
60-Second Pitch
"The brute force tries every sequence of coins, which grows exponentially with the amount. I define dp[w] as the fewest coins that make the amount w. Only dp[0] = 0 is real, and every other amount starts at infinity, which means not reachable yet. For each coin, I loop w upward and set dp[w] to the smaller of its value and dp[w - coin] + 1. The upward loop lets dp[w - coin] already include this coin, so a coin can repeat. There are N coins and the amount as the number of sums, so the time is O(N * amount) and the space is O(amount). If the problem asks for the number of ways, I start with dp[0] = 1 and keep the coins in the outer loop, so each combination is counted once."
Common Questions
- Why does the forward loop allow a coin to repeat?
When the loop reaches
dp[w], the smaller indexw - coinwas already updated in this pass, so it may already include the coin. Using it again adds one more copy of the same coin. A downward loop reads the old value, so each coin is used at most once.- Does the order of the two loops matter?
- What are the time and space complexity?
O(N * amount) time and O(amount) space, where
Nis the number of coins. It is pseudo-polynomial, because it grows with the value of the amount, not with its number of digits.- Why not take the largest coin first?
A greedy choice is wrong for some coin sets. With coins
[1, 3, 4]and amount 6, greedy picks 4 + 1 + 1, which is 3 coins, and the best is 3 + 3, which is 2 coins. The table checks every coin for every amount, so it does not make that mistake.- How does Perfect Squares (LC 279) use this?
The items are the squares 1, 4, 9 and so on up to
n, each usable any number of times, and the goal is the fewest items that add up ton. It iscoin_changewith those squares as the coins. Forn = 12the answer is 3, namely 4 + 4 + 4. Forn = 13it is 2, namely 4 + 9.
SWE Reasoning
Spot it
- You build a target amount from items, and each item can be used any number of times: coins, squares, step sizes.
- The question asks for the fewest items, or for the number of ways to reach the amount.
- The amount is small enough to be an array index.
- The statement says whether the order of the items matters. If it does not, count combinations. If it does, count sequences.
- A greedy choice of the largest coin fails on some coin sets, so a table is needed. With coins
[1, 3, 4]and amount 6, the best answer is 3 + 3, and greedy gives 4 + 1 + 1.
The invariant, step by step
dpstarts as infinity for every amount, anddp[0] = 0. Only the amount 0 is reachable before any coin.- The outer loop takes one coin. At this moment
dp[w]is correct for all coins before it. - The inner loop visits each amount
wfromcoinup toamount. - The update
dp[w] = min(dp[w], dp[w - coin] + 1)readsdp[w - coin], which this pass may already have updated. So the coin can be used again. - When the outer loop ends,
dp[w]is the fewest coins that makewwith all coins, each any number of times, which is the card's invariant. - The code returns
dp[amount], or -1 if it is still infinity.
Traps
- Loop downward when items can repeat. Each coin is used at most once.
coin_change([2], 4)returns -1 instead of 2. - Put the amounts in the outer loop to count combinations. Each order is counted separately. For Coin Change II (LC 518) with amount 3 and coins
[1, 2]the result is 3 instead of 2. - Fill
dpwith 0 instead of infinity in a minimum problem. Every amount looks reachable with 0 coins.coin_change([2], 3)returns 0 instead of -1. - Forget the -1 at the end. If
dp[amount]is still infinity, returning it as a number gives a wrong or invalid answer. - Use a greedy choice. Taking the largest coin first fails for
coins = [1, 3, 4]and amount 6.