Given a list of coin denominations and a target amount, find the fewest coins needed to make that amount (coin change).
Define dp[i] as the minimum coins to make amount i. For each amount from 1 to target, try every coin: if the coin value is at most i, dp[i] = min(dp[i], 1 + dp[i - coin]). Base case dp[0] = 0. Initialise all other entries to infinity so valid solutions propagate cleanly.
How to think about it
Recognise the pattern
The signal is “minimum (or maximum) number of items to reach a target” with unlimited reuse of items. This is the unbounded knapsack family of DP problems. Two hallmarks: overlapping subproblems (making change for 11 cents reuses solutions for 9, 10 cents, etc.) and optimal substructure (the best way to make 11 cents is 1 coin + the best way to make the remainder).
Define the DP
- State:
dp[i]= minimum number of coins to make amounti. - Recurrence:
dp[i] = min(dp[i - c] + 1)for each coincwherec <= i. - Base case:
dp[0] = 0(zero coins needed for amount 0). - Initialisation:
dp[i] = infinityfori > 0(not yet reachable).
Build the approach step by step
Brute force / greedy (always pick the largest coin that fits) fails for tricky denominations. For coins=[1,3,4], target=6: greedy picks 4+1+1=3 coins, but optimal is 3+3=2 coins.
Recursive with memo works: min_coins(amount) = 1 + min(min_coins(amount - c) for c in coins if c <= amount). Memoising makes it O(amount × len(coins)).
Bottom-up tabulation fills the table left to right — no recursion, no stack:
coins=[1,2,5], amount=11
dp: [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
1 2 3 4 5 6 7 8 9 10 11
after filling:
dp: [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3 ]
^5 ^10 ^5+5 ^5+5+1Complexity
- Time — O(amount × len(coins)): two nested loops, each bounded above.
- Space — O(amount): the dp array. No additional recursion stack.