更弱智的算法学习day 37

完全背包

完全背包问题和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])