The problem
Given coin values coins (as many of each as you like) and an amount, return the fewest coins that add up to exactly amount, or −1 if it cannot be made.
Examples
01
- Input
coins = [1, 2, 5], amount = 11
- Output
3
02
- Input
coins = [2], amount = 3
- Output
-1
03
- Input
coins = [1], amount = 0
- Output
0
Constraints
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2³¹ − 1
- 0 ≤ amount ≤ 10⁴
The idea
Taking the biggest coin first can fail: with coins 1, 3, 4 and amount 6, greedy gives 4 + 1 + 1 (three coins) but 3 + 3 is two.
Instead, let fewest[x] be the fewest coins making x. The last coin used is some c, and what is left, x − c, must itself be made as cheaply as possible: fewest[x] = 1 + the smallest fewest[x − c] over coins c ≤ x. Fill it from 0 (which needs none) up to amount; an amount no coin combination makes stays at “infinity” — here, amount + 1, more coins than could ever be needed.
- Time
- O(amount × number of coins)
- Space
- O(amount)
Solution
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # fewest[x]: the fewest coins making x. The last coin is some c, so # fewest[x] = 1 + min(fewest[x - c]) over every coin c <= x. INF = amount + 1 # more coins than could ever be needed fewest = [0] + [INF] * amount for x in range(1, amount + 1): for c in coins: if c <= x and fewest[x - c] + 1 < fewest[x]: fewest[x] = fewest[x - c] + 1 return -1 if fewest[amount] == INF else fewest[amount]