题目

题解

class Solution:def change(self, amount: int, coins: List[int]) -> int:# 状态定义：dp[i][j]表示用前i种硬币，刚好凑齐面额j的方法有多少dp = [[0 for i in range(amount+1)] for j in range(len(coins)+1)]# base casefor i in range(len(coins)+1):dp[i][0] = 1# 状态转移for i in range(1, len(coins) + 1):for j in range(1, amount + 1):# 第i枚硬币的面值小于要凑齐的面额，可以选择「用」和「不用」# 注意这里的判断条件是>=，与背包问题里的>有区别。if j - coins[i-1] >= 0:dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]# 否则不能用else:dp[i][j] = dp[i-1][j]return dp[len(coins)][amount]