今日专题：动态规划 完全背包（每个物品可以选n次）
动态规划分析的时候把状态转移图画出来
先遍历物品再遍历背包求排列数，先遍历背包再遍历物品求组合数
518. 零钱兑换 II
class Solution:def change(self, amount: int, coins: List[int]) -> int:@cachedef dfs(i, j):if j <= 0:return 1if i < 0:return 0if coins[i] > j:return dfs(i - 1, j)return dfs(i - 1, j) + dfs(i, j - coins[i])return dfs(len(coins) - 1, amount)377. 组合总和 Ⅳ
class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:# 怎么处理不同排序是不同的结果呢# dp[i][j]=dp[i-1][j]+dp[i][j-nums[i]]size = len(nums)dp = [[0 for _ in range(target + 1)] for _ in range(size)]for i in range(size):dp[i][0] = 1for n in range(1, target + 1):for m in range(size):if n >= nums[m]:dp[m][n] = dp[m - 1][n] + dp[-1][n - nums[m]]else:dp[m][n] = dp[m - 1][n]return dp[size - 1][target]
