322. Coin Change
Overview
Find the minimum number of coins needed to make up a given amount. This is the classic unbounded knapsack problem where each coin denomination can be used unlimited times.
Algorithm Steps
- Initialize
dparray of sizeamount + 1withinf(impossible state) - Set
dp[0] = 0(0 coins needed for amount 0) - For each coin value
v:- For each amount
vvfromvtoamount:dp[vv] = min(dp[vv], dp[vv - v] + 1)
- For each amount
- Return
dp[amount]if reachable, else-1
Complexity
| Metric | Complexity | Reason |
|---|---|---|
| Time Complexity | Nested loops: coins () × amount () | |
| Space Complexity | DP array of size amount + 1 |
Implementation
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [inf] * (amount + 1)
dp[0] = 0
for v in coins:
for vv in range(v, amount + 1):
dp[vv] = min(dp[vv], dp[vv - v] + 1)
return -1 if dp[amount] == inf else dp[amount]Example
coins = [1, 2, 5]
amount = 11
# Initialize: dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
# Process coin = 1:
# dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
# Process coin = 2:
# dp[2] = min(2, dp[0] + 1) = 1
# dp[3] = min(3, dp[1] + 1) = 2
# dp[4] = min(4, dp[2] + 1) = 2
# ...
# dp = [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
# Process coin = 5:
# dp[5] = min(3, dp[0] + 1) = 1
# dp[6] = min(3, dp[1] + 1) = 2
# dp[7] = min(4, dp[2] + 1) = 2
# dp[10] = min(5, dp[5] + 1) = 2
# dp[11] = min(6, dp[6] + 1) = 3
# dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
result = 3 # 5 + 5 + 1 = 11Key Points
- Unbounded knapsack: each coin can be used multiple times
- Bottom-up DP: builds solutions for smaller amounts first
- Order matters: iterating coins in outer loop allows reuse (unbounded)
- Inner loop direction: forward iteration enables multiple uses of same coin
- Return
-1whendp[amount]remainsinf(impossible to form amount)
Related Problems
- 518. Coin Change II - count number of combinations (not minimum)
- 279. Perfect Squares - same pattern with square numbers as "coins"