代码随想录算法训练营第四十一天|1049.最后一块石头的重量II、494.目标和、474.一和零

本文主要是介绍代码随想录算法训练营第四十一天|1049.最后一块石头的重量II、494.目标和、474.一和零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1049.最后一块石头的重量II

思路：将石头分为两堆，他们两个的重量最接近，碰撞的话，此时剩下的重量最小，故此时想到动态规划，但是我个人感觉很容易被陷入本道题的一些条件，比如说x<=y，想着要去区分每次拿出去的顺序什么的。这道题的关键是生成的dp[target]的含义是能从石头堆中取出的最靠近target的值。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum=0;for(int i=0;i<stones.size();++i){sum+=stones[i];}int 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.目标和

思路：这道题要将目标和进行分解，分解成一个小数和一个大数，但是这两个数的和是一定的，即left+right=sum，right-left=target，这样的一个关系，那么right=sum-left==>left=(sum+target)/2，故这个left就是要求的值。若不能分解成left，那么可知是不可能通过加减运算得到结果的。记一个key:dp[j]+=dp[j-nums[i]];求组合的递推公式标准写法！

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;int bagsize=(target+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];}
};

474.一和零

思路：二维的01背包问题，统计每个字符串中的0和1，然后利用递推公式进行dp[i][j]=max(dp[i][j],dp[i-zeronum][j-onenum]+1)得到每个dp[i][j]的最大子集！

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 s:str){if(s=='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];}
};