01背包问题总结
首先，需要清楚的是0/1背包问题本身：有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
此处使用动态规划求解，问题的划分方式为：使用一个二维数组对问题进行两部分的划分。对于 dp[i][j] 求解的是，当背包容量为 j 时，在物品 0-i 中选择能够获取到的最大的容量。
那么在采取逐行遍历的方式，就是每一次增加物品的数量，递推公式为： dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i])
采取逐列遍历的方式，每一次增加的是背包的容量，那么递推公式为： dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i])
使用滚动数组实现动态规划的过程：基于背包容量的滚动数组实现，那么此处就一定要先遍历物品再遍历背包了，因为动态规划数组的含义是，在第 i 次迭代中，使用 0-i 个物品去填充背包，能够得到的背包中物品的最大价值。并且是0/1背包问题，那么对于背包的遍历顺序一定要是
能否基于物品数量的滚动数组实现：
动态规划数组的定义：定义数组
dp[n]，在初始时表示，当背包容量为0时，能够装下的最大的物品价值。动态规划数组的推导：对于第
j次迭代时，表示当背包容量为j时，能够装下的物品的最大价值。在一维的情形下，背包容量减去weight[i]的情形无法实现递推。
因此在0/1背包中使用滚动数组，只能基于背包容量的数组来实现。
LeetCode 416 分割等和子集
给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
此处的重点是问题的转化，要求两个子集的元素和相等，将元素的和转化为背包的大小，也就是使用一个容量等于全部元素和一半的背包去装数组元素能否恰好将背包装满。这一半能够装满，那么另外一半也能够装满。也就完成了划分。
动态规划数组的定义为： dp[j] 表示：当背包容量为 j 时，能够恰好将背包装满，那么递推公式就为：在第 i 次迭代中在 0-i 个元素中进行选择，dp[j]=dp[j]||dp[j-nums[i]] 此处的背包也是需要从后向前遍历，为了防止重复选择。
本题的重点在于问题的转化，将等和子集划分，转化为一个0/1背包问题。
LeetCode 1049 最后一块石头的重量II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y 。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回0。
本题的求解方式也是需要对问题进行转化，两块石头粉碎后的重量一定是小重量石头的两倍，那问题就像是一个消消乐游戏。那么想要找到最优的方案，就是将石头划分为两个集合，这两个集合的石头总重量要尽可能的接近。
最接近的划分方式就是：两个集合的总重量恰好为全部石头总重量的一半，转为背包容量为sum/2，能否将背包恰好装满。定义动态规划数组 dp[sum/2+1] ，表示能否恰好将 sum/2 容量的背包装满，那么最后只要找到能够恰好装满的最大容量的背包即可。问题和分割等和子集类似。
LeetCode 494 目标和
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 + 或 - ，然后串联起所有整数，可以构造一个表达式：
例如，nums = [2, 1] ，可以在 2 之前添加 + ，在 1 之前添加 - ，然后串联起来得到表达式 +2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。
本题对于问题的转化是相对复杂的：首先，假设在表达式中为负号元素的总和为 neg ，所有元素的总和为 sum ，那么就有 sum-neg-neg=target ，那么就有 neg=(sum-neg)/2 此处 sum<target 或 (sum-target)%2==1 说明没有可行方案。
那么讲问题转化为：将容量为 neg 的背包装满有多少种方案。依旧是使用基于滚动数组的动态规划实现，先便利物品在遍历背包，背包从后向前遍历。此处主要是递推公式存在区别 dp[j]=dp[j]+dp[j-nums[i]] 此处的含义在于：包含的方案有在第 i 次迭代时，不选择 nums[i] 的方案 dp[j] 和选择 nums[i] 的方案 dp[j-nums[i]]
LeetCode 474 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集 。
此处也是一个0/1背包问题，但是将背包的容量转变为了2维，此处每一个物品的价值都为1，那么创建一个二维数组，基于滚动数组的方式实现。那么依旧是在第 k 次迭代中，在元素 0-k 中进行选择。递推公式 dp[i][j]=max(dp[i][j],dp[i-k0][j-k1]+1) 也就是在第 k 迭代中，比较选取元素 strs[k] 或者不选择，哪一个能够获得最大长度。