当前位置：首页 > ds >正文

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

ds 2025/7/18 0:23:14

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

讲解：代码随想录

思路：

01背包问题：题意说要求粉碎石头后留下的最小石头重量，石头粉碎的规则是两个石头如果重量相等，同时粉碎，如果重量不相等，粉碎后的重量是大减小。抽象成背包问题，就是尽可能装满总石头重量一半的背包，此时粉碎的最彻底，为什么粉碎的更彻底，因为尽可能装满石头重量一半的背包，这样能装进背包的这部分，就会对应另一半的部分同时粉碎，此时剩下的就是无法粉碎的石头

代码：

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(3000,0);int sum = 0;for(int i =0 ;i<stones.size();i++){sum+=stones[i];}int target = sum/2;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];}
};

遇到的问题：

1.对于背包问题的抽象，背包的容量是多少，是石头总重量的一半。

494. 目标和

思路：

01背包问题：通过left（正的部分） - right（负的部分）=target，设 right = sum -left，所以target = left - （sum-left)，所以left = （target+sum）/2，sum和target为固定值，就可以求解了。然后转化为背包问题，就是用nums数组里的数，装满left大小容量的背包，有多少的方法

代码：

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(abs(target) > sum)return 0;if((sum+target)%2 == 1)return 0;int bagsize = (sum+target)/2;vector<vector<int>> dp(nums.size(),vector<int>(bagsize+1,0));//注意二维数组的初始化方式//dp数组初始化if(nums[0]<=bagsize)dp[0][nums[0]] = 1;dp[0][0] = 1;int numzero = 0;for(int i =0;i<nums.size();i++){if(nums[i]==0)numzero++;dp[i][0] = pow(2.0,numzero);//幂运算函数，2.0是底数，numzero是指数}for(int i =1;i<nums.size();i++){for(int j = 0;j <= bagsize;j++){if(nums[i]>j)dp[i][j] = dp[i-1][j];else dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j];}}return dp[nums.size()-1][bagsize];}
};

遇到的问题：

1.对于01背包的抽象问题非常难想，并且求出left部分的组合方式的方法数，就相当于求出left和right的组合方法数，比较难想

474. 一和零

思路：

01背包：如何抽象成背包问题？因为要求指定m个0和n个1，的最大子集。m个0和n个1看作背包的容量，此题特殊的是，背包的容量是一个二维的，两个值。

代码：

滚动数组法

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));int zeronum = 0,onenum = 0;for(string str : strs){for(char c : str){if(c == '0')zeronum++;else onenum++;}}for(int i = m ;i>=z)}
};