Coin Change
Medium
Array
Dynamic Programming
BFS
You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money. Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return `-1`. You may assume that you have an infinite number of each kind of coin.
Example 1
Input: coins = [1,5,6,9], amount = 11
Output: 2
Explanation: 11 = 5 + 6
Example 2
Input: coins = [2], amount = 3
Output: -1
Example 3
Input: coins = [1], amount = 0
Output: 0

Constraints

  • •1 <= coins.length <= 12
  • •1 <= coins[i] <= 2³¹ - 1
  • •0 <= amount <= 10⁴
Time Complexity
O(amount × coins)
Space Complexity
O(amount)
14
Case 1
Input: [1,5,6,9] 11
Expected: 2
Case 2
Input: [2] 3
Expected: -1