本文主要是介绍代码随想录算法训练营第四十一天|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];}
};
这篇关于代码随想录算法训练营第四十一天|1049.最后一块石头的重量II、494.目标和、474.一和零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
