Coin Change
Medium1-D dynamic programming
You have coins of the values in coins, as many of each as you need. Return the fewest coins that add up to exactly amount.
Return -1 if no mix of coins makes that amount. An amount of 0 needs no coins.
Examples
Input: coins = [1, 4, 5], amount = 8 Output: 2
4 + 4. Starting with the 5 leaves 3, which takes three 1s: four coins.
Input: coins = [3, 7], amount = 5 Output: -1
No mix of 3s and 7s adds up to 5.
Constraints
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 2³¹ - 10 ≤ amount ≤ 10⁴
Stuck?
Hint 1
Always taking the biggest coin that fits can miss the best answer. Instead, work out the fewest coins for every amount from 0 up to amount.
Hint 2
For each amount a, try every coin c ≤ a: the answer is one more than the best for a - c. Start every amount at Infinity, and amount 0 at 0.
The idea
The best mix for an amount ends with some coin, and what is left before that coin must itself be made with the fewest coins. So the answer for an amount is one more than the best answer for that amount minus one of the coins. Work it out for every amount from 0 up, so the smaller answers are ready when a larger one needs them.
Time O(amount · coins.length)Extra space O(amount)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
fewest[t] will hold the fewest coins that make exactly t. Infinity marks an amount nothing makes yet, and it loses every Math.min. Amount 0 needs no coins, and every mix is built up from it.
function coinChange(coins, amount) { const fewest = new Array(amount + 1).fill(Infinity); fewest[0] = 0; for (let total = 1; total <= amount; total++) { for (const coin of coins) { if (coin <= total) { fewest[total] = Math.min(fewest[total], fewest[total - coin] + 1); } } } return fewest[amount] === Infinity ? -1 : fewest[amount];}The trap
Taking as many of the biggest coin as fit, then the next biggest, works for everyday money, which is why it feels right. With other coin values the biggest coin can leave a remainder that needs many small coins, while a mix of middle-sized coins is shorter. It can also return -1 for an amount that skipping the big coin would have made exactly.
function coinChange(coins, amount) { const sorted = [...coins].sort((a, b) => b - a); let count = 0; let left = amount; for (const coin of sorted) { count += Math.floor(left / coin); left %= coin; } return left === 0 ? count : -1; // biggest coin first is not always best}