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

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

代码随想录算法训练营

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

---

---

前言

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

讲解文档

LeetCode 494. 目标和

讲解文档

LeetCode 474.一和零

讲解文档

---

一、LeetCode1049. 最后一块石头的重量 II

1.题目链接

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

2.思路

（1）尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题---->尽可能接近一半—>在总质量小于等于质量和/2的情况下，让质量尽可能大，得到一堆的质量，sum-dp结果为另外一堆的质量
（2）01背包问题
背包质量上限：target（质量和的一半）
物品价值：stones[i]
物品质量：stones[i]

3.题解

二维

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n=stones.size();int sum=0;for(int i=0;i<n;i++){sum+=stones[i];}vector<vector<int>>dp(n+1,vector<int>(sum,0));int target=sum/2;for(int i=stones[0];i<=target;i++){dp[0][i]=stones[0];}for(int i=1;i<n;i++){for(int j=0;j<=target;j++){if(j<stones[i])dp[i][j]=dp[i-1][j];else dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);}}return sum-dp[n-1][target]-dp[n-1][target];}
};

一维

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

二、LeetCode 494. 目标和

1.题目链接

LeetCode 494. 目标和

2.思路

（1）设前面取+的元素之和为x，前面取-的元素之和为sum-x。target=x-(sum-x),解出来x=(target+sum)/2
其中，有两个情况无解：
1）target的绝对值大于sum；
2）target+sum为奇数
（2）01背包问题
1）物品质量：nums[i]
物品价值：nums[i]
包的最大容积：X
dp[j]表示包里面物品质量和为J时，有几种方法
2）状态转移
使得包里面物品质量和为J有n种可能性（可能是加上了nums[0]~nums[n-1]使得总质量j），所以方法数是这些可能性方法数总和
3）初始化
dp[0]=1：在质量为0时，只有不装这一种办法
4）遍历：一维01背包的遍历法
i从小到大，j从大到小

3.题解

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int n=nums.size();int sum=0;for(int i=0;i<n;i++){sum+=nums[i];}if(abs(target)>sum || (sum+target)%2==1)return 0;int x=(sum+target)/2;vector<int>dp(x+5,0);dp[0]=1;for(int i=0;i<n;i++){for(int j=x;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[x];}
};

三、LeetCode 474.一和零

1.题目链接

LeetCode 474.一和零

2.思路

（1）看成有两层的0-1背包，m和n本质上是背包两个层各自的最大容量

• 容量为m的层存放1，容量为n的层存放0
• 物品质量：1（一个字符串为一个物品）
• 物品重量：0,1个数
  （2）dp[i][j]：背包两层重量分别为i,j时，最大字符串数

（3）遍历
1）遍历物品：遍历数组中的字符串
2）遍历容量：遍历m和n，从后向前

3.题解

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(n + 5, vector<int>(m + 5, 0));int s = strs.size();// mn是背包的两个容量，可以看成背包有两层dp[0][0] = 0;for (int r = 0; r < s; r++) {int min0 = 0;int min1 = 0;for (int k = 0; k < strs[r].size(); k++) {if (strs[r][k] == '0')min0++;elsemin1++;}for (int i = n; i >= min1; i--) {for (int j = m; j >= min0; j--) {dp[i][j]=max(dp[i][j],dp[i-min1][j-min0]+1);}}}return dp[n][m];}
};

---

这篇关于代码随想录算法训练营第 36 天 |LeetCode1049. 最后一块石头的重量 II LeetCode 494. 目标和 LeetCode 474.一和零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---