Coin Change (Minimum Coins)
Given coin denominations and an amount, return the fewest coins to make it, or −1.
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.
Unbounded knapsack: coins may be reused, so the state is just the amount and every coin is retried at every amount. The tell that it's DP rather than greedy is that taking the largest coin first can fail — with coins [1, 3, 4] and amount 6, greedy picks 4+1+1 while the answer is 3+3. Whenever a locally best choice can be beaten later, enumerate.
Approach
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.
Define the subproblem
dp[a] = minimum coins for amount a; dp[0] = 0, everything else ∞ until proven.
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.
Solution & live demo
Common pitfalls
Taking the largest coin greedily
for c in sorted(coins, reverse=True):
while amount >= c:
amount -= c; count += 1for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1Greedy is only valid for canonical coin systems. On coins = [1, 3, 4], amount = 6 it returns 3 (4+1+1) when 2 (3+3) is optimal. The DP tries every coin at every amount, so no better combination can be missed.
Initialising the table to zero
dp = [0] * (amount + 1)
dp = [0] + [INF] * amount
Zero means "reachable with no coins", which is true only for amount 0. Elsewhere it makes unreachable amounts look free and the minimum never rises above 0. Everything except the base case starts unreachable.
Returning dp[amount] without the reachability check
return dp[amount]
return dp[amount] if dp[amount] != INF else -1
Amounts that cannot be formed at all — coins = [2], amount = 3 — keep their infinite sentinel, and the problem asks for -1 there. Returning the sentinel leaks an internal marker as if it were an answer.
Edge cases
dp[0]=0 — zero coins.
dp stays ∞ → −1.