解题步骤
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
01背包注意事项
二维dp：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])一维dp：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
为什么呢？
倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15dp[2] = dp[2 - weight[0]] + value[0] = 30此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）dp[1] = dp[1 - weight[0]] + value[0] = 15所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
那么问题又来了，为什么二维dp数组遍历的时候不用倒序呢？
因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！
背包问题分类
从集合的角度理解DP数组
DP:
完全背包：
上面的方程为0-1背包
下面的方程为完全背包
多重背包不能采用完全背包的方式优化
