Coin Change
Fewest coins to make an amount. Greedy fails on coin sets like {1,4,5}; DP builds the answer for every amount from 0 up, trying each coin at each step.
- Category
- Dynamic Programming
- Time complexity
- O(n·amount)
- Space complexity
- O(amount)
Pseudocode
dp[0] ← 0 dp[a] ← min over coins of dp[a−c] + 1 (greedy fails; DP tries all) answer at dp[amount]
Reference implementation
dp = [0] + [None] * amount
for a in range(1, amount + 1):
dp[a] = min(dp[a - c] + 1
for c in coins if a >= c)