class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
# INF 表示无效
INF = 0x3f3f3f
dp = [INF]*(amount+1)
# 初始化
# 为啥初始化 dp[0] = 0
# 表示使用coins组成0元的方法有几种?
dp[0] = 0
for i in range(1, amount+1):
for c in coins:
# 如果使用coin 来组合数据
if i>=c:
dp[i] = min(dp[i-c]+1,dp[i])
if dp[amount] == 0x3f3f3f:
return -1
return dp[amount]
网友评论