代码随想录算法训练营第四十三天

今日事争取今日毕！还一天就上班啦，陪产假结束，坚持坚持！

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] = 0if (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];}
};