1049.最后一块石头的重量 II
本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。
视频讲解：https://www.bilibili.com/video/BV14M411C7oV
Tips：其实只要把石头分成重量尽可能相等的两堆就可以了，所以和昨天的最后一题是一样的思路。
我的题解：
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for(int i = 0; i<stones.size();i++){
sum += stones[i];
}
int half = sum / 2;
vector<int> dp(half + 1);
dp[0] = 0;
// stones数组既是重量也是价值
for(int i = 0; i<stones.size();i++){
for(int j = half; j >= stones[i]; j--){
dp[j] = max(dp[j],dp[j - stones[i]] + stones[i]);
}
}
return (sum - dp[half]) - dp[half];
}
};494. 目标和
大家重点理解 递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。
视频讲解：https://www.bilibili.com/video/BV1o8411j73x
https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
Tips：这道题有两个点比较不容易想到
1. 将有正有负的问题，通过加上sum变成只求正的元素，这一步很巧妙
如何转化为01背包问题呢。
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为，装满容量为x的背包，有几种方法。
这里的x，就是bagSize，也就是我们后面要求的背包容量。
大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。
这么担心就对了，例如sum 是5，S是2的话其实就是无解的，所以：
（C++代码中，输入的S 就是题目描述的 target）
if ((S + sum) % 2 == 1) return 0; // 此时没有方案同时如果 S的绝对值已经大于sum，那么也是没有方案的。
（C++代码中，输入的S 就是题目描述的 target）
if (abs(S) > sum) return 0; // 此时没有方案再回归到01背包问题，为什么是01背包呢？
因为每个物品（题目中的1）只用一次！
这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
2. 递推公式有变化。在求装满背包有几种方法的情况下，递推公式一般为：
dp[j] += dp[j - nums[i]];我的题解：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 正的数相加等于 (target + sum) / 2，只需要求有几种组合相加等于这个值即可
int sum = 0;
for(int i = 0; i<nums.size(); i++){
sum+=nums[i];
}
if((target + sum)%2 == 1){
// 如果这个值带0.5的话，是无解的
return 0;
}
if(abs(target) > sum){
// 如果target大于总和的话，也是无解的
return 0;
}
int positive = (target + sum) / 2;
vector<int> dp(positive+1,0);
dp[0] = 1;
for(int i = 0; i<nums.size(); i++){
for(int j = positive; j>=nums[i]; j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[positive];
}
};474.一和零
通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。
视频讲解：https://www.bilibili.com/video/BV1rW4y1x7ZQ
https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
Tips：这道题还是01背包的思路，唯一区别就是背包有两个袋子，一个装0，一个装1而已。
我的题解：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i = 0; i<strs.size(); i++){
int num0 = 0;
int num1 = 0;
for(int j = 0; j<strs[i].size(); j++){
if(strs[i][j] == '0'){
num0++;
}
else{
num1++;
}
}
for(int j = m; j>=num0;j--){
for(int k = n; k>=num1; k--){
dp[j][k] = max(dp[j][k],dp[j-num0][k-num1]+1);
}
}
}
return dp[m][n];
}
};