You are given an array coins of distinct coin denominations and an integer amount. Return the fewest number of coins needed to make up amount exactly. If it cannot be made, return -1. You have unlimited coins of each denomination.
Example 1
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 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] <= 100000 <= amount <= 10000Note: the greedy strategy of always taking the largest coin fails — try coins = [1,3,4], amount = 6.
Input
coins = [1,2,5], amount = 11
Expected
3
4 hidden tests run on submit