Greedy fails here — and that failure motivates one of the most important algorithmic techniques: dynamic programming.
Given coin denominations and a target amount, find the minimum number of coins needed to make that amount. If it's impossible, return -1.
# coins=[1,5,11], amount=15 → 3 (5+5+5)
# coins=[2], amount=3 → -1 (impossible with only 2s)
# coins=[1,2,5], amount=11 → 3 (5+5+1)Greedy says: always take the largest coin that fits. This works for real currency (1, 5, 10, 25 cents) but fails for arbitrary denominations.
# coins = [1, 5, 11], amount = 15
#
# Greedy: take 11 (largest ≤ 15). Remaining: 4.
# take 1 four times. Total: 5 coins.
#
# Optimal: take 5 three times. Total: 3 coins.
#
# Greedy gives 5. Correct answer is 3. Greedy is wrong.The problem requires considering all possibilities. Dynamic programming builds the solution bottom-up, reusing subproblem results so we never compute the same thing twice.
Top-down: for each amount, try every coin and take the minimum result. Cache results to avoid recomputation.
from functools import lru_cache
def coin_change_memo(coins, amount):
@lru_cache(maxsize=None)
def dp(rem):
if rem == 0: return 0
if rem < 0: return float('inf')
return 1 + min(dp(rem - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coin_change_memo([1, 5, 11], 15)) # 3Build an array dp where dp[i] = minimum coins to make amount i. Start from 0 and fill up to the target.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins needed to make amount 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 -1
print(coin_change([1, 5, 11], 15)) # 3
print(coin_change([2], 3)) # -1
print(coin_change([1, 2, 5], 11)) # 3| Property | Value |
|---|---|
| Time | O(amount × len(coins)) |
| Space | O(amount) for the dp array |
# dp[0] = 0 (base case)
# dp[1] = dp[0]+1 = 1 (use coin 1)
# dp[2] = dp[1]+1 = 2
# dp[3] = 3
# dp[4] = 4
# dp[5] = dp[0]+1 = 1 (use coin 5)
# dp[6] = dp[5]+1 = 2 (use coin 1 on top of 5)
# ...
# dp[10] = dp[5]+1 = 2 (5+5)
# dp[11] = min(dp[10]+1, dp[0]+1) = 1 (use coin 11!)
# dp[12] = dp[11]+1 = 2
# dp[13] = dp[12]+1 = 3 (11+1+1) but also dp[8]+1...min is 3
# dp[14] = 3
# dp[15] = min(dp[14]+1, dp[10]+1, dp[4]+1) = min(4,3,5) = 3 ✓ (5+5+5)dp[i] = 1 + min(dp[i - coin]) for all coins ≤ i. We initialize with inf so that impossible amounts naturally propagate as infinity and the final check catches them.