Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Coin Change

LeetCode #322Medium
dp[a] = 1 + min(dp[a − coin]) · fewest coins to make amount

Given an array of coin denominations and a target amount, return the fewest number of coins needed to make up that amount. Each coin may be used unlimited times. If the amount cannot be made, return −1.

Asked atAmazonGoogleUber
step 1 / 13
·
·
·
·
·
·
·
Why greedy fails
▸
1// greedy: always take the largest coin that fits
2// coins [1, 3, 4], amount 6 → 4 + 1 + 1 = 3 coins
3// but optimal is 3 + 3 = 2 coins → greedy is wrong
state
  • coins[1, 2, 5]
  • amount6
  • greedy ideatake largest coin first

line 1Instinct says “grab the biggest coin that fits, repeat.” For coins [1, 2, 5] making 6 that even works: 5 + 1 = 2 coins. But greedy is NOT correct in general — the largest coin can box you in.