Coin Change Fewest Count
Problem Description
You are given an array of coin denominations `coins` and an integer `amount` representing a total monetary value. Return the **minimum number of coins** needed to make up exactly `amount`. If it is impossible to reach exactly `amount` using the given coins, return `-1`.
You may use each coin denomination **as many times** as you like.
**Example 1:**
```
Input: coins = [2, 5, 7], amount = 14
Output: 2
Explanation: 7 + 7 = 14 (2 coins)
```
**Example 2:**
```
Input: coins = [3, 6, 9], amount = 11
Output: -1
Explanation: No combination of 3, 6, 9 sums to 11.
```
Constraints
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 1000
- 0 <= amount <= 10000
- All values in coins are distinct.
Follow-up
Can you solve this using memoised top-down recursion instead? How does the call-stack depth compare to the iterative approach for large `amount`?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.