这道题和第三十三天的题的解法差不多，只不过这次不用判断dp[target]是否等于target了，而是求dp[target]最大是多少。这道题要求剩下石头最小的质量是多少，那么就把他们分成两半，两半的重量足够接近的时候，剩下石头最小的质量就越接近0，因此求出背包容量为sum/2的背包，最多能装多少重量的石头，然后拿这个值减去sum可得到另外一半的重量 两个相减即可得到最终的结果。
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001, 0);
int sum = 0;
for (int i = 0; i < stones.size(); i++) sum += stones[i];
int target = sum / 2;
for (int i = 0; i < stones.size(); i++) { // 遍历物品
for (int j = target; j >= stones[i]; j--) { // 遍历背包
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};
在回溯算法系列中，一起学过这道题目回溯算法：39. 组合总和 (opens new window)的录友应该感觉很熟悉，这不就是组合总和问题么？因为只有两个选择 +或者- 因此可以暴力回溯解答出来 但是时间会超时。下面是回溯的代码。
class Solution {
public:
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, int& result, int target) {
if (path.size() == nums.size()) {
int sum = accumulate(path.begin(), path.end(), 0);
if (sum == target) result++;
}
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1, result, target);
path.pop_back();
path.push_back(-nums[i]);
backtracking(nums, i + 1, result, target);
path.pop_back();
}
}
int findTargetSumWays(vector<int>& nums, int target) {
int result = 0;
backtracking(nums, 0, result, target);
return result;
}
};这道题目的数可以分为两个集合 一个全是正数一个全是负数
假设加法的集合总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为，装满容量为x的背包，有几种方法，也就是装满正数的集合有几种方法。剩下的就是负数的集合
这里的x，就是bagSize，也就是我们后面要求的背包容量。 并且如果(target + sum) / 2不能整除的话那么说明就无法凑成结果为sum的正负数集合。
再回归到01背包问题，为什么是01背包呢？
因为每个物品（题目中的1）只用一次！
这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
1. 确定dp数组以及下标的含义
dp[j] 表示：nums[0]到nums[i]的数据里填满j（包括j）这么大容积的包，有dp[j]种方法
2. 确定递推公式
有哪些来源可以推出dp[j]呢？
只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，
- 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
- 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
- 已经有一个3（nums[i]） 的话，有 dp[2]种方法 凑成 容量为5的背包
- 已经有一个4（nums[i]） 的话，有 dp[1]种方法 凑成 容量为5的背包
- 已经有一个5 （nums[i]）的话，有 dp[0]种方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - 0nums[i]] 累加起来。
所以求组合类问题的公式，都是类似这种：
dp[j] += dp[j - nums[i]]3. dp数组如何初始化
背包容量0理解成什么都装不下就是0，理解成只有什么都不装就是1，这里要求的是装法，所以dp[0]初始化为1。
4. 遍历顺序
我们讲过对于01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。
从前nums[i]的数据里取数能填满dp[j]的方法数
完整代码如下：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(S) > sum) return 0; // 此时没有方案
if ((S + sum) % 2 == 1) return 0; // 此时没有方案
int bagSize = (S + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};这道题的背包的容量有两个维度，不是以前的只有一个维度，因此dp数据应该是二维的了（其实是三维的，如果不是滚动数组的话）这两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
zeroNumh和oneNum是当前装入的str的0的个数和1的个数类似于01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
01背包为什么一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
那么本题也是，物品就是strs里的字符串，背包容量就是题目描述中的m和n。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
for (string str : strs) { // 遍历物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};
