代码随想录算法训练营第37天|完全背包理论基础、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯（进阶版）
打卡Day37
- 1.完全背包理论基础
- 2.518.零钱兑换II
- 3.377. 组合总和 Ⅳ
- 4.70. 爬楼梯（进阶版）
1.完全背包理论基础
题目链接：完全背包理论基础
文档讲解： 代码随想录
01背包和完全背包的区别：
01背包中每个物品只能使用一次，而完全背包中可以重复使用，每种物品有无数件。
这点不同会体现在遍历顺序上，直接针对遍历顺序进行分析。01背包的内部循环遍历背包容量时是从后往前的，为了确保每个物品只被加入一次。而在纯完全背包问题中，这个内部循环是从前往后的，因为每个物品可以重复使用。同时，对于纯完全背包问题，可以先遍历物品后背包，也可以先背包后物品。因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。而对于01背包问题，如果两层循环对调，每个dp[j]只能放入一个物品。
kind, bagweight = [int(x) for x in input().split()]
weight = []
value = []
for _ in range(kind):a, b = [int(x) for x in input().split()]weight.append(a)value.append(b)dp = [0] * (bagweight + 1)
for i in range(kind):for j in range(weight[i], bagweight + 1):dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bagweight])
2.518.零钱兑换II
题目链接：518.零钱兑换II
文档讲解： 代码随想录
（1）确定数组和下标
这道题硬币的重量和价值相等，总金额 j 可以抽象为容量为 j 的背包装满的价值为 j。所求的是装满背包的方法数量。dp[ j ] 表示背包容量为 j 装满的方法数。
（2）递推关系式
遍历到 coins[ i ] 时，dp[ j ] += dp[j - coins[i]]
（3）初始化
dp[0] = 1，不然往后递推都为0
（4）遍历顺序
先物品后背包
（5）打印数组
class Solution(object):def change(self, amount, coins):""":type amount: int:type coins: List[int]:rtype: int"""dp = [0] * (amount + 1)dp[0] = 1for i in range(len(coins)):for j in range(coins[i], amount + 1):dp[j] += dp[j - coins[i]]return dp[amount]
我忽略的一个点是在遍历顺序上的细节，这道题中求的是组合数，而不是排列数，这两种情况的遍历顺序是不一样的。例如，coins[0] = 1, coins[1] = 5。先遍历物品后背包求的是组合数，先放入1进行计算，在放入5进行计算。而先背包后物品是排列数，因为每次外层的背包循环，都会经过1和5的计算，会包含{1，5}和{5，1}两种情况。
3.377. 组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ
文档讲解： 代码随想录
（1）确定数组和下标
dp[ j ]表示和为 j 的组合个数
（2）递推关系式
dp[ j ] += dp[ j - nums[ i ] ]
（3）初始化
sp[0] = 1，为0后续递推都为0
（4）遍历顺序
因为顺序不同的序列被视为不同的组合，因此时排列问题，先背包后物品，均从前往后遍历
（5）打印数组
class Solution(object):def combinationSum4(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""dp = [0] * (target + 1)dp[0] = 1for j in range(1, target + 1):for i in range(len(nums)):if j >= nums[i]:dp[j] += dp[j - nums[i]]return dp[target]
4.70. 爬楼梯（进阶版）
题目链接：70. 爬楼梯（进阶版）
文档讲解： 代码随想录
（1）确定数组和下标
dp[ j ] 表示爬 j 个台阶的方法数
（2）递推关系式
dp[ j ] += dp[ j - i ]
（3）初始化
dp[0] = 1，其余位置为0，因为要做累加
（4）遍历顺序
排列问题，先背包后物品，都从前往后
（5）打印数组
n, m = [int(x) for x in input().split()]
dp = [0] * (n + 1)
dp[0] = 1
for j in range(1, n + 1):for i in range(1, m + 1):if j >= i:dp[j] += dp[j - i]
print(dp[n])