MediumBlind75ArrayDP
Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins needed to make up that amount.
Examples
Input
coins = [1,5,10,25], amount = 30
Output
2
5 + 25 = 30, using 2 coins.
Input
coins = [2], amount = 3
Output
-1
It's impossible to make 3 with only coin of value 2.
Constraints
- •
1 <= coins.length <= 12 - •
1 <= coins[i] <= 2^31 - 1 - •
0 <= amount <= 10^4
Approaches
Try all combinations of coins.
CodeT: O(n^amount) | S: O(amount)
def coin_change(coins, amount):
def helper(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
min_coins = float('inf')
for coin in coins:
result = helper(remaining - coin)
min_coins = min(min_coins, result + 1)
return min_coins
result = helper(amount)
return result if result != float('inf') else -1Build up from 0 to amount using dynamic programming.
CodeT: O(amount * len(coins)) | S: O(amount)
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1Same DP approach with early termination.
Diagram
coins = [1,5,10,25], amount = 30
dp[0]=0, dp[1]=1, dp[2]=2, ..., dp[5]=1
..., dp[25]=1, dp[30]=2 (5+25)
CodeT: O(amount * len(coins)) | S: O(amount)
def coin_change(coins, amount):
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] <= amount else -1Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force - Recursion | O(n^amount) | O(amount) | Try all combinations of coins. |
| DP - Bottom Up | O(amount * len(coins)) | O(amount) | Build up from 0 to amount using dynamic programming. |
| Optimized DP | O(amount * len(coins)) | O(amount) | Same DP approach with early termination. |
Brute Force - Recursion
T: O(n^amount)S: O(amount)
Try all combinations of coins.
DP - Bottom Up
T: O(amount * len(coins))S: O(amount)
Build up from 0 to amount using dynamic programming.
Optimized DP
T: O(amount * len(coins))S: O(amount)
Same DP approach with early termination.
Common Mistakes
Using recursion without memoization
Not handling the case where amount cannot be made
Using float('inf') incorrectly in comparisons