Greedy fails here: with coins [1, 3, 4] and amount 6, taking the biggest coin first gives 4+1+1 (three coins) but 3+3 is better. Dynamic programming fixes this by computing the best answer for every smaller amount first.
Given a list of coin denominations coins and an integer amount, return the fewest coins needed to make up that amount. You have an unlimited supply of each coin. If the amount cannot be made, return -1.
Examples
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 5 + 5 + 1
Input: coins = [2], amount = 3
Output: -1
Input: coins = [1], amount = 0
Output: 0
Constraints
1 <= len(coins) <= 12,1 <= coins[i] <= 2**31 - 10 <= amount <= 10**4- Target: O(amount * len(coins)) time
Goals
- Define a DP state as 'fewest coins to make amount a' and fill it bottom-up
- Use an 'infinity' sentinel for unreachable states
- See why the greedy 'take the biggest coin' approach fails