You're given coin denominations coins and a target amount. Return the fewest coins needed to make exactly amount, or -1 if it can't be done.
You have an unlimited supply of every denomination.
Examples
Example 1
- Input
- coins = [1, 2, 5], amount = 11
- Output
- 3
- Why
- 11 = 5 + 5 + 1.
Example 2
- Input
- coins = [2], amount = 3
- Output
- -1
Example 3
- Input
- coins = [1], amount = 0
- Output
- 0
Constraints
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4