|
题目：
代码：
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# 比如是只有两个硬币面值，并且两个硬币的数量是无限的，当无限取硬币时，转移方程：pro[n] += proi[n-coin[i]] 为什么是+=, 因为比如你使用面值为1时的组合方案在计算使用面值为2的方案时，应该是初始值；
# 时间复杂度：O(amount*coins_n)
# 空间复杂度：O(amount)
dp = [0] * (amount+1) # 初始的金额组合方案都应该是为0，且金额包含0和amount；所以应该定义amount+1
dp[0] = 1 # 作为参考值使得后续转移方程正确， 比如当使用一分面值时，dp[1] = dp[1] + dp[1-1]; 明显amount=1时应该有一种方案，又初始dp[1]=0，所以dp[0]=1
coins_n = len(coins)
for i in range(coins_n): # 因为硬币是无限数量的所以针对硬币循环，背包容量由小变大
for j in range(coins[i], amount+1): # 因为当金额小于当前使用的面值时，不会使用
dp[j] += dp[j-coins[i]]
return dp[amount]
| 
转播
