今日事争取今日毕！还一天就上班啦，陪产假结束，坚持坚持！
1049. 最后一块石头的重量 II
思路主要是分成两个差不多大的两堆，所以需要用尽可能一半去减另一半即可。思路很重要啊，第一次确实想不明白。
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
int target = 0;
for(int i = 0;i < stones.size();i++){
sum += stones[i];
}
target = sum/2;
vector<int>dp(target + 1,0);
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];
}
};494. 目标和
如何转化为01背包问题呢。
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
理解上面的内容，才能转化成背包问题。
#include <cmath>
#include <iostream>
#include <vector>
using namespace ::std;
class Solution
{
public:
int findTargetSumWays(vector<int> &nums, int target)
{
int sum = 0;
for (int i = 0; i < nums.size(); i++)
sum += nums[i];
if ((sum + target) % 2 == 1)
return 0; // 和是奇数，肯定是没有正好合适的方案
if (abs(target) > sum)
return 0; // target过大，远超sum，肯定没有方案
int bagSize = (target + sum) / 2;
vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));
// 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1
// 其他情况dp[0][j] = 0
if (nums[0] <= bagSize)
dp[0][nums[0]] = 1;
// 初始化最左列（dp[i][0])
// 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案
// n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）
int numZeros = 0;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == 0)
{
numZeros++;
}
dp[i][0] = pow(2, numZeros);
}
for (int i = 1; i < nums.size(); i++)
{
for (int j = 1; j < bagSize + 1; j++)
{
if (j < nums[i])
dp[i][j] = dp[i - 1][j];
else
{
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
}
// for (int i = 0; i < nums.size(); i++)
// {
// for (int j = 0; j < bagSize + 1; j++)
// {
// cout << " " << dp[i][j];
// }
// cout << endl;
// }
return dp[nums.size() - 1][bagSize];
}
};
int main()
{
Solution syz;
vector<int> nums1;
int xx[3] = {1, 2, 1};
for (int i = 0; i < 3; i++)
{
nums1.push_back(xx[i]);
}
syz.findTargetSumWays(nums1, 0);
}这步在二维表里异常关键，相当于保证能把方法叠加起来。
if (nums[0] <= bagSize)
dp[0][nums[0]] = 1;一维表目前是理解随想录的思想，不过还没默写过。先摘抄下来
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];
}
};494. 目标和
还是没有完成今天的工作，我歇一歇，明天继续。
没有深挖为什么一定是从后向前遍历，不过感觉和上一题相似，都是通过前面的内容为基础，加到后面的。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>>dp(m+1,vector<int>(n+1,0));
for(string str : strs){
int ZeroNum = 0;
int OneNum = 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];
}
};