动态规划练习八（01背包问题）
一、问题介绍与解题心得
01背包问题就是每个物品数量只有一个，每个物品可以取或不取，来达到收益最大，或者收益在某个值。
限制条件：背包容量有限，物品个数只有1个
解决问题：从价值入手（价值最大或是某个值），从容量入手（不超过最大体积还是刚好装到某一个体积）
设的 dp 表一般是 dp[i][j] 表示在 [1, i] 的物品中选择，符合要求 j 的价值
此处以01背包模板题为例：【模板】01背包_牛客题霸_牛客网
1、传统方法
这里根据要求的不同用两个 dp 表解决问题，分析过程不赘述，主要看总结的规律。
由于01背包中物品个数只有一个，所以选不选 i 物品都是去看 dp[i - 1] 位置的值，所以要进行空间优化的话就是用 dp[i - 1][j] 和 dp[i - 1][j - v[i]] 来更新 dp[i] 的值，而我们现在只有一个一维数组，此时要开始更新 dp[i] 那么一维数组中必然存放的是已经更新完成的 dp[i - 1]，那已知我们要更新的 dp[i] 是需要旧的一维数组表中的，相对于 j 位置之前的值，所以 dp[i] 的更新一定是从后向前的更新，防止覆盖。
所以总结，01背包问题的空间优化是删去行元素，从后向前更新。
2、空间优化
二、例题
1、分割等和子集
416. 分割等和子集 - 力扣（LeetCode）
2、目标和
494. 目标和 - 力扣（LeetCode）
3、最后一块石头重量2
1049. 最后一块石头的重量 II - 力扣（LeetCode）
三、总结
其实01背包问题就是要你把问题转化成在一段数据里面取出一部分数据满足条件。数据只有一个。
难点就是如何转化成取数据，如第二第三题就是把符号的正负选择转化成在一段数据中取出一些正数来满足题目要求。