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
The trap baked into this question is the greedy instinct — grab the biggest coin that fits, repeat. The interviewer almost always picks denominations where greedy fails, so what they are really checking is whether you recognise that “fewest items to reach a target, with unlimited reuse” is the unbounded-knapsack DP, not a greedy walk.
Two hallmarks put it in DP territory. Overlapping subproblems: making 11 reuses the answers for 9 and 10. Optimal substructure: the best way to make 11 is one coin plus the best way to make the remainder. So define dp[i] as the minimum coins for amount i, with dp[0] = 0 (zero coins make zero) and every other entry seeded to infinity, meaning “not yet reachable.” Then for each amount you try every coin c that fits and ask whether dp[i - c] + 1 beats the best you have. Filling the table left to right means dp[i - c] is always already final by the time you read it — no recursion, no stack.
A worked example
def coin_change(coins, amount):
INF = float('inf')
dp = [INF] * (amount + 1)
dp[0] = 0 # base case: amount 0 needs 0 coins
for i in range(1, amount + 1):
for c in coins:
if c <= i and dp[i - c] + 1 < dp[i]:
dp[i] = dp[i - c] + 1 # one coin c, plus best for the rest
return dp[amount] if dp[amount] != INF else -1 # unreachable -> -1
print(coin_change([1, 2, 5], 11)) # 5 + 5 + 1
print(coin_change([2], 3)) # impossible with only 2s
print(coin_change([1, 3, 4], 6)) # 3 + 3 beats greedy's 4 + 1 + 1
print(coin_change([1], 0)) # edge: amount is 03
-1
2
0Each line earns its number. Eleven cents from {1,2,5} needs three coins (5+5+1). Three cents from only {2} is impossible, so dp[3] stays infinite and the function returns -1. The third line is the headline: greedy on {1,3,4} would take 4+1+1 = 3 coins, but the DP finds 3+3 = 2 because it considers every coin at every amount, not just the largest. And amount 0 returns 0 straight from the base case without entering the loop.