You have coins worth each of the values in coins, as many of each as you like. Return the
fewest coins that add up to exactly amount, or -1 if no combination of coins does.
An amount of 0 takes no coins.
Example 1
- Input
- coins = [1, 2, 5], amount = 11
- Output
- 3
Example 2
- Input
- coins = [2], amount = 3
- Output
- -1
Example 3
- Input
- coins = [1, 3, 4], amount = 6
- Output
- 2
Constraints
coinsholds 1 to 12 different values.- 1 ≤
coins[i]≤ 10⁴ - 0 ≤
amount≤ 10⁴
Show the pattern
Dynamic programming (1D)
The fewest coins for an amount is one coin plus the fewest for what is left, and the same smaller amounts come up again and again: a table indexed by amount answers each of them once.
See dynamic programming (1d) in a visualiserShow the approach
Let fewest[a] be the fewest coins that make the amount a. Whatever the best way to make a
is, it has a last coin c, and the coins before it make a − c as cheaply as possible. So
fewest[a] = 1 + min(fewest[a − c]) over every coin c ≤ a, with fewest[0] = 0.
Fill the table from 1 up to amount. Use amount + 1 to mean "can't be made": no real answer
needs that many coins, since every coin is worth at least 1. If fewest[amount] is still
amount + 1 at the end, return -1.
Time: O(amount × k) for k coins · Space: O(amount)