Coin Change
MediumDynamic programming
You have coins 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 does. An amount of 0 needs 0 coins.
Constraints
- 1 ≤ length of
coins≤ 12 - 1 ≤
coins[i]≤ 100,000, all different - 0 ≤
amount≤ 10,000
Example 1
Input
coins = [1,2,5]
amount = 11
Output
3
Why:
5 + 5 + 1.
Example 2
Input
coins = [2]
amount = 3
Output
-1
Why:
Coins of 2 only make even amounts.
Example 3
Input
coins = [1]
amount = 0
Output
0
Why:
Nothing to pay.
Hints
Was this a good challenge?
- Solved by
- 0
- Submissions
- 0
- Accepted
- –