完全背包：
文章链接
题目链接：卡码网 52.携带研究材料
与01背包的区别在于物品数量无限，因此同一种物品可以取多次。
递推式如下：
- 二维：dp[i][j] = max(dp[i - 1][j], dp[i][j - weights[i]] + value[i])，因为同样物品数量无限，因此选了该物品后剩下背包容量的最大价值应当为dp[i][j - weight[i]] + value[i]，即当前行的，因为第 i 个物品还可以继续选
- 一维：dp[j] = max(dp[j], dp[j - weights[i]] + value[i])
遍历顺序：
无论是一维数组还是二维数组，遍历背包和物品的先后顺序无所谓，但是遍历背包要顺序遍历，因为已经选了的物品后面还可以继续选。
class Solution():
# 一维数组
def bagWeightOne(self):
N, bagweight = [int(x) for x in input().split()]
weights, value = [], []
for _ in range(N):
w, v = [int(x) for x in input().split()]
weights.append(w)
value.append(v)
dp = [0] * (bagweight + 1)
for i in range(N):
for j in range(weights[i], bagweight + 1):
dp[j] = max(dp[j], dp[j - weights[i]] + value[i])
return dp[bagweight]
# 二维数组
def bagWeightTwo(self):
N, bagweight = [int(x) for x in input().split()]
weights, value = [], []
for _ in range(N):
w, v = [int(x) for x in input().split()]
weights.append(w)
value.append(v)
dp = [[0] * (bagweight + 1) for _ in range(N)]
# 初始化
for j in range(weights[0], bagweight + 1):
dp[0][j] = dp[0][j - weights[0]] + value[0]
# 递推
for i in range(1, N):
for j in range(0, bagweight + 1):
if j >= weights[i]:
# 注意max的第二个参数
dp[i][j] = max(dp[i - 1][j], dp[i][j - weights[i]] + value[i])
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1]
solution = Solution()
print(solution.bagWeightTwo())
感悟：
因为完全背包同一物品可以选多次，联系到01背包一维数组时背包容量逆序为了让物品只选一次，因此完全背包一维数组背包容量为顺序，再联系到递推式，因此先背包容量后物品还是先物品后背包容量都可以，但是需要顺序遍历背包容量
518.零钱兑换 Ⅱ：
文章链接
题目链接：518.零钱兑换 Ⅱ
思路：
本题是要求组合数，因此dp数组保存的也应当为组合数
动规五部曲：
- ① dp数组及下标的含义
dp[j] : 可以凑成背包容量（总金额）为 j 的硬币组合数为dp[j] - ② 递推式
dp[j] += dp[j - coins[i]] - ③ 初始化
dp[0]初始化为1，可以认为总金额为0时可以凑成总金额的组合数为1，其余非0下标初始化为0 - ④ 遍历顺序
本题要求的是组合数，如果先遍历背包容量后遍历物品的话，以[1, 5]为例，背包容量的每个值，都经过了1和5的计算，得到了{1, 5}和{5, 1}两种情况，计算的是排列数；如果先遍历物品后遍历背包的话，还是以[1, 5]为例，那么得到的方法数量只有{1, 5}一种情况，此时计算的是组合数
因此要采用先物品后背包容量的遍历顺序 - ⑤ 举例
以[1, 2, 5]，amount = 5举例
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for j in range(coin, amount + 1):
dp[j] += dp[j - coin]
return dp[amount]
感悟：
完全背包应用的先后遍历顺序
LeetCode 377.组合总和Ⅳ：
文章链接
题目链接：377.组合总和Ⅳ
思路
分析本题可知，nums数组中的数可以多次选择，因此是完全背包，且顺序不同的序列被视为不同的组合，因此还是排列问题。
整体思路与上题相似，不同之处在于本题要求排列数，因此是先遍历背包容量后遍历物品
初始化部分因为nums为正数，所以dp[0]无意义，为例便于递推初始化为1，其余非0初始化为0，避免初始化数对递推结果产生影响
举例
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 num in nums:
if num <= j:
dp[j] += dp[j - num]
return dp[target]
感悟：
先仔细分析题目再敲代码
70.爬楼梯(进阶版)：
文章链接
题目链接：卡码网 57.爬楼梯
思路：
首先分析题目，物品（每次可以爬的台阶数）为1-m，对应的重量和价值也为1~m，背包容量为n，且物品可以重复使用，因此是完全背包问题。
且先爬2阶再爬1阶和先爬1阶再爬2阶不同，因此为排列数，先遍历背包容量再遍历物品。
动态规划五部曲：
- ① dp数组及下标的含义
dp[j] : 爬 j 阶台阶的的方法数为dp[j] - ② 递推式
如果最后爬 i 阶台阶到了 j 阶台阶，方法数为dp[j - i](条件 j >= i)
如果最后爬 < i 阶台阶到了 j 阶台阶，方法数为dp[j]
因为题目需要的是多少不同的方法数，即排列总数
dp[j] += dp[j - i] - ③ 初始化
因为每次爬的台阶数都为正数，因此dp[0]无意义，为了便于递推，因此dp[0]初始化为1，其余下标非0初始化为0，避免初始值对递推结果造成影响 - ④ 遍历顺序
先遍历背包容量（需要的台阶数）再遍历物品（每次爬的台阶数）。 - ⑤ 举例
以m = 2, n = 3举例
class Solution():
def climbStair(self, m, n):
if m >= n:
return 1
dp = [0] * (n + 1)
dp[0] = 1
# 求排列数，先遍历背包容量后遍历物品
# 也可以这么理解，爬 i 阶台阶后到达 j 阶台阶的方法为dp[j - i]
for j in range(1, n + 1):
# 递推公式需要i <= j,且i <= m
for i in range(1, min(j + 1, m + 1)):
dp[j] += dp[j - i]
return dp[n]
n, m = [int(x) for x in input().split()]
solution = Solution()
print(solution.climbStair(m, n))
感悟：
先分析题目（01背包、完全背包、组合、排列、求最大值？）后确定动规五部曲。
学习收获：
- 完全背包问题及完全背包问题在组合、排列数上的应用。
- 完全背包问题是单个物品可以取多次，因此遍历顺序中遍历背包容量时为顺序遍历（一维数组）。
- 同时需要分析完全背包应用问题是求最大值还是求组合数、排列数。如果是求组合数，那么应当先遍历物品再遍历背包容量；如果求排列数，应当先遍历背包容量再遍历物品。
以[1, 5]举例，先物品后背包的话，只会出现{1, 5}一种情况
先背包后物品的话，会出现{1, 5}和{5, 1}两种情况 - 同时所给物品的weight和value的范围来确定如何初始化
