【代码随想录训练营】【Day 46】【动态规划-6】| Leetcode 518, 377

• 完全背包 组合问题，先物品后重量
• 代码随想录思路：组合 和 排列

class Solution:def change(self, amount: int, coins: List[int]) -> int:# 金额 i 的 组成方式数量dp = [0] * (amount + 1)dp[0] = 1for coin in coins:for i in range(coin, amount + 1):dp[i] += dp[i-coin]return dp[amount]

• 完全背包：排列问题，先重量后物品

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:# 总和为 i 的组合个数dp = [0] * (target+1)dp[0] = 1for i in range(1, target+1):for num in nums:if i >= num:dp[i] += dp[i-num]return dp[target]