274. Coin Change
You are given the coin denominations of a currency in the integer array coins, with an unlimited supply of each denomination, plus a target value amount.
Your function receives coins and amount and returns a single integer: the fewest coins whose values add up to exactly amount. If no combination of these denominations can total amount, return -1. Making an amount of 0 takes 0 coins.
Beware: always grabbing the largest coin that fits does not give the minimum.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1 uses three coins, and no two coins can reach 11.
Example 2:
Input: coins = [2], amount = 3
Output: -1
Explanation: Sums of 2-coins are always even, so 3 is unreachable.
Constraints:
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 10⁴
- 0 ≤ amount ≤ 10⁴
Hints:
Greedy fails: with coins [1, 3, 4] and amount 6, taking the biggest coin first gives 4 + 1 + 1 (three coins), but 3 + 3 does it in two.
Think of amounts as nodes and each coin as a step of size c. Starting from 0, what is the smallest number of steps that lands exactly on amount?
Define best(a) = fewest coins making amount a. Any optimal pile for a has some last coin c, and removing it leaves an optimal pile for a - c. So best(a) = 1 + min over coins c <= a of best(a - c), with best(0) = 0. Fill a table from 0 up to amount.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: coins = [1, 2, 5], amount = 11
Expected output: 3