解题思路
状态：
dp[i] = 组成金额i需要的最小金币数
方程：
dp[i] = min(dp[i - coin[x]]) + 1
0<=x<len(coins)
代码
1
2
3
4
5
6
7
8
9
10
| class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('INF')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin > i:
continue
dp[i] = min(dp[i], dp[i-coin] + 1)
return dp[amount] if dp[amount] != float('INF') else -1
|