Coin Change — unbounded knapsack, minimum coins

You have coin denominations [1, 2, 5] and need to make 11. Greedy says 5+5+1 = three coins. Greedy fails on [1, 3, 4] making 6: it grabs 4 then two 1s (three coins), missing 3+3 (two coins). DP fixes this by considering every choice at every amount.

The pattern

Let dp[a] = min coins to make amount a. For each amount, try every denomination — if the coin fits, the answer is dp[a - c] + 1. Take the min across coins.

Base case: dp[0] = 0. Everything else starts at a sentinel amount + 1 (larger than any real answer). At the end, sentinel = -1.

This is the unbounded knapsack template: unlimited copies of each item, minimize an objective. Contrast with 0/1 knapsack where each item is used at most once.

Loop order

For min coins it doesn't matter. But for counting ways:

• Amounts outside, coins inside → permutations (1+2 ≠ 2+1).
• Coins outside, amounts inside → combinations (1+2 = 2+1).

Interviewers ask both. Remember the fix is a single line swap.

Common pitfalls

• Greedy shortcuts. US/INR coin systems happen to be canonical (greedy works). Arbitrary denominations require DP.
• Off-by-one on table size. Need amount + 1 slots.
• Negative or zero coin values aren't handled — validate inputs.

Complexity

Time O(amount × len(coins)); space O(amount). Pseudo-polynomial — scales with the value, not the input bits.

Try it

1. Write coin_change_ways(coins, amount) returning number of distinct combinations. Test ([1, 2, 5], 5) → 4 ways.
2. Modify coin_change to also return one optimal list of coins used.