52. 携带研究材料（第七期模拟笔试）
本题是完全背包问题，也就是在遍历的时候，当前物品可以被重复使用。
前面dp被修改了之后后面索引的dp值可以在此基础上进行更新，而0-1背包则需要在上一个物品的基础上进行更新，所以必须保证前面的值不被修改，只能从后往前遍历。
和0-1背包相比，只是遍历顺序不同。
和0-1背包从大到小（bagweight 到 weight[i]）遍历背包容量不同，完全背包从（weight[i] 到 bagweight）。
此外本题还需要注意输入模式的写法。
num, bagweight = map(int, input().split())
wupin = [list(map(int, input().split())) for _ in range(num)] # 注意这里的封装形式
dp = [0] * (bagweight+1)for i in range(num):for j in range(wupin[i][0], bagweight+1): # 正序遍历，从能够装得下这个物品开始（前面都是0）dp[j] = max(dp[j], dp[j-wupin[i][0]] + wupin[i][1])print(dp[-1])518. 零钱兑换 II
本题是目标和的一个完全背包的变种。
需要注意递推公式的写法 dp[j] += dp[j - coin]；也就是在本coin没有进入背包时候的方法数，在进入这个硬币之后+1。
关于组合数/排列数：和遍历顺序有关。如果是先背包后物品，则是排列数，因为在同一个背包状态下，会出现先装第一个再装第二个的情况。如果是组合数，则是先物品后背包，因为这种情况下，每次只看一个物品，且不会返回到上一个物品，所以只能按照题目给定的物品顺序依次放入。
class Solution(object):def change(self, amount, coins):""":type amount: int:type coins: List[int]:rtype: int"""dp = [0]*(amount+1)dp[0] = 1 # 对于计数问题需要初始化为1for coin in coins:for j in range(coin, amount+1): # 先物品后背包，求的是组合数，先背包后物品，求的是排列数dp[j] += dp[j - coin]return dp[-1]57. 爬楼梯（第八期模拟笔试）
本题是爬楼梯的动态规划解法。
与凑目标数不同，爬楼梯求解的是排列数的个数。所以在遍历顺序上是：先遍历背包大小（1到bagweight）再遍历物品大小（0到weight）。
本题的背包大小就是楼层，物品大小就是每次能爬的楼梯数。
初始化dp[0] = 1，规定爬0层也是1个解法（实际上不输出，仅仅是为了递推）。
floor, Step = map(int, input().split())
dp = [0] * (floor+1)
dp[0] = 1
# 本题是排列数，所以先遍历背包容量，再遍历物品
for j in range(1, floor+1):for step in range(Step+1):dp[j] += dp[j-step]
print(dp[-1])动态规划的主要题型和转化汇总
本周小结！（动态规划系列四） | 代码随想录
Day43完结！！！
