Coin Change

LeetCode

You are given an integer array coins and an integer amount. Return the fewest number of coins needed to make up that amount. If it is not possible, return -1.

1def coinChange(coins: List[int], amount: int) -> int:
2    dp = [amount + 1] * (amount + 1)
3    dp[0] = 0
4    
5    for a in range(1, amount + 1):
6        for c in coins:
7            if a - c >= 0:
8                dp[a] = min(dp[a], 1 + dp[a - c])
9    
10    return -1 if dp[amount] == amount + 1 else dp[amount]
Previous
House Robber
Next
Longest Increasing Subsequence
0
0
7
1
7
2
7
3
7
4
7
5
7
6
coins=[1, 3, 4]
amount=6
Step 1 / 6
Step 1:
dp[a] = min coins to make amount a. Initialize dp[0]=0, others=amount+1 (∞).
Focus: select @ [0]
amount=6