完全背包
完全背包问题和01背包的区别主要在“物品可以重复添加”这里。在代码上的区别只有，可以重复选择一个物品；也正是我们在01背包里要注意的，可以选择一个物品，也即内存循环可以从前往后遍历
# 输入 n, bag_weight = map(int, input().split()) weight = [] value = [] for _ in range(n): w, v = map(int, input().split()) weight.append(w) value.append(v) dp = [0] * (bag_weight+1) for i in range(0,n): for j in range(0,bag_weight+1): if j >= weight[i]: dp[j] = max(dp[j] , dp[j-weight[i]]+ value[i]) print(dp[bag_weight])518. 零钱兑换 II
dp函数的意义：
对应dp[amount]而言，其意义是：当还需要amount面额需要补充时，存在能凑成amount的金额的硬币组合数。
状态转移方程：
也即存在选或不选两种情况：
不选i：dp[i] = dp[i]
选了i：dp[i] = dp[i-1]
因此 dp[j] += dp[j-i]
遍历顺序：
因为是完全背包问题，因此先遍历硬币，在遍历金额，顺序遍历
初始化：
由于金额为0时，有1中选择方法，也即全不选。故dp[0]=1
class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0]*(amount+1) dp[0] = 1 for i in coins: for j in range(i, amount+1): dp[j] += dp[j-i] return dp[amount]377. 组合总和 Ⅳ
dp函数的意义：
对应dp[target]而言，其意义是：存在一个目标整数target时，从nums中找出的元素排列个数为dp[target]个
状态转移方程：
也即存在选或不选两种情况：
不选i：dp[i] = dp[i]
选了i：dp[i] = dp[i-1]
因此 dp[j] += dp[j-i]
遍历顺序：
因为是完全背包问题，且是求排列数，因此先便利整数，在遍历数组从而实现顺序不同也可以保存下来
初始化：
因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。
dp[0]=1
class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0] * (target+1) dp[0] = 1 for j in range(1, target+1): for i in nums: if j >= i: dp[j] += dp[j-i] return dp[target]70. 爬楼梯 （进阶）
dp函数的意义：
对应dp[n]而言，其意义是：存在一个台阶数n时，从m中找出的楼梯排列个数为dp[n]个
状态转移方程：
也即存在选或不选两种情况：
不选i：dp[i] = dp[i]
选了i：dp[i] = dp[i-1]
因此 dp[j] += dp[j-i]
遍历顺序：
因为是完全背包问题，且是求排列数，因此先便利总数，在遍历数组从而实现顺序不同也可以保存下来
初始化：
因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。
dp[0]=1
n,m = map(int, input().split()) dp = [0] * (n+1) dp[0] = 1 for j in range(1,n+1): for i in range(1,m+1): if i <= j: dp[j] += dp[j-i] print(dp[n])
