The fewest coins that add up to an amount. Greedy fails, so build up from zero, reusing the best answer for each smaller amount.
▼The problem
LeetCode 322 (Medium). Given coin denominations and an amount, return the fewest coins that add up to the amount, or -1 if it can't be made. There is an unlimited supply of each coin.
Example: coins [1, 3, 4], amount 6 → 2 (3 + 3).
The solution
from math import inf
def coin_change(coins, amount):
dp = [0] + [inf] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] < inf else -1Transcript
Coin Change. Given coin values and an amount, return the fewest coins that add up to it, or minus one if you can't. Each coin can be reused.
Take coins one, three and four, and amount six. Greedy grabs the biggest coin first: four, one, one. Three coins. But three plus three needs just two.
Try every combination: pick a coin, then solve what's left. For six: twenty four calls. For thirty, two and a half million. The same small amounts get solved again and again.
Instead, build up from zero. Line up a jar for every amount, zero to six. Jar zero needs no coins. For any other jar, try each coin that fits: one coin, plus the best jar for what's left. Keep the smallest.
In code, the table starts with zero, then infinity. For each amount and each coin that fits, keep the smaller of the current entry and the entry for amount minus coin, plus one. Still infinity at the end? Return minus one.
Let's fill the jars. One: one coin. Two: one plus one. Three and four: a single coin each. Five: four plus one. Six: a one coin plus jar five makes three. A three coin plus jar three makes two. A four coin plus jar two makes three. Best is two: three plus three.
Each amount tries each coin, so the time is amount times coins, and one row of jars is the space.
Small amounts first, then build up. That's Coin Change.