Coin Change
Medium
Dynamic ProgrammingBFS
You are given an integer array `coins` representing different denominations and an integer `amount` representing a total amount of money.
Return the **fewest number of coins** needed to make up that amount. If that amount cannot be made up, return `-1`. You may assume infinite supply of each coin denomination.
**Example 1:**
```
Input: coins = [1,5,10,25], amount = 30
Output: 2
Explanation: 25 + 5 = 30
```
**Example 2:**
```
Input: coins = [2], amount = 3
Output: -1
```
Expected Time Complexity
O(n * amount)
Expected Space Complexity
O(amount)
Example Test Cases
Example 1
Input:
[1,5,10,25] 30
Output:
2
Example 2
Input:
[2] 3
Output:
-1