Coin Change
MediumDynamic Programming · Microsoft
You are given a list of distinct coin denominations coins and a target amount. You have an unlimited supply of every denomination.
Return the fewest number of coins whose values add up to exactly amount. If no combination of coins adds up to amount, return -1. An amount of 0 needs 0 coins.
Example 1
- Input:
- coins = [1, 3, 4], amount = 6
- Output:
- 2
- Explanation
- Two
3coins make 6. Grabbing the largest coin first (4) leaves 2, which costs two1coins, for 3 coins in total, so greedy is not optimal.
Example 2
- Input:
- coins = [4, 6], amount = 9
- Output:
- -1
- Explanation
- Every coin is even, so any total they make is even. 9 is odd and cannot be formed.
Example 3
- Input:
- coins = [2, 5, 10, 1], amount = 27
- Output:
- 4
- Explanation
- Two
10coins, one5and one2make 27 with 4 coins. No combination of 3 coins reaches 27.
Constraints
- 1 ≤
coins.length≤ 12 - 1 ≤
coins[i]≤ 231 - 1 - All values in
coinsare distinct - 0 ≤
amount≤ 104