Description
Intuition
Utilize bottom up tabulation.
- Set base case of index 0 to 0. It takes 0 coins to sum to 0 amount.
- Iterate from 1 to amount checking if amount - coin is >= 0. If it is then:
- Update this amount/index to the minimum of current value & amount - coin + 1
Diagram
-----Example 1coins = [1,2,5]amount = 11-----Index: 0 1 2 3 4 5 6 7 8 9 10 11DP : [ 0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12] ^New DP: [ 0, 1 ] * (1) 1 coinNew DP: [ 0, 1, 1 ] * (1) 2 coinNew DP: [ 0, 1, 1, 2 ] * (1) 1 coin & (1) 2 coinNew DP: [ 0, 1, 1, 2, 2 ] * (2) 2 coinsNew DP: [ 0, 1, 1, 2, 2, 1 ] * (1) 5 coinNew DP: [ 0, 1, 1, 2, 2, 1, 2 ] * (1) 5 coin & (1) 1 coinNew DP: [ 0, 1, 1, 2, 2, 1, 2, 2 ] * (1) 5 coin & (1) 2 coinNew DP: [ 0, 1, 1, 2, 2, 1, 2, 2, 3 ] * (1) 5 coin & (1) 2 coin & (1) 1 coinNew DP: [ 0, 1, 1, 2, 2, 1, 2, 2, 3, 3 ] * (1) 5 coin & (2) 2 coinsNew DP: [ 0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2 ] * (2) 5 coinsNew DP: [ 0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3] * (2) 5 coins & (1) 1 coinCode
1class Solution:2 def coinChange(self, coins: List[int], amount: int) -> int:3 dp = [amount+1] * (amount+1)4 dp[0] = 05 for a in range(1, amount+1):6 for c in coins:7 if a - c >= 0:8 dp[a] = min(dp[a], dp[a-c]+1)9 return dp[amount] if dp[amount] != amount+1 else -1