Coin Change (Minimum Coins)
Given coin denominations and an amount, return the fewest coins to make it, or −1.
02
Intuition
Greedy (largest coin first) fails for sets like [1,3,4] making 6. But 'fewest coins for amount a' only depends on fewest coins for smaller amounts: dp[a] = 1 + min(dp[a − coin]). Build up from 0.
03
Approach
1
Where greedy breaks
[1,3,4], amount 6: greedy 4+1+1 = 3 coins, optimal 3+3 = 2. Local best isn't global best → DP.
2
Define the subproblem
dp[a] = minimum coins for amount a; dp[0] = 0, everything else ∞ until proven.
3
Fill bottom-up
For each a from 1..amount try every coin: dp[a] = min(dp[a], dp[a−c] + 1). Unreachable amounts stay ∞ → return −1.
04
Solution & live demo
python
▶1class Solution:
▶2 def coinChange(self, coins, amount):
▶3 INF = float("inf")
▶4 dp = [0] + [INF] * amount
▶5 for a in range(1, amount + 1):
▶6 for c in coins:
▶7 if c <= a and dp[a - c] + 1 < dp[a]:
▶8 dp[a] = dp[a - c] + 1
▶9 return dp[amount] if dp[amount] != INF else -1
05
Edge cases
amount = 0
dp[0]=0 — zero coins.
Unreachable amount, e.g. coins=[2], amount=3
dp stays ∞ → −1.
06
Complexity
Time
O(amount × coins)
Space
O(amount)
Classic unbounded-knapsack shape.