代码随想录训练营打卡第36天|1049.最后一块石头的重量II 494.目标和 474.一和零
1049.最后一块石头的重量II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
题目链接
个人题解
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum=0;
for(auto i:stones) sum+=i;
int load = sum/2;
vector<int> dp(150001,0);
for(int i=0;i<stones.size();i++){
for(int j=load;j>=stones[i];j--){
dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return sum-2*dp[load];
}
};
复杂度分析
- 时间复杂度：n^2
- 空间复杂度：n
解题思路
和昨天的切割子串一样的思路，依旧是找一半，关键在于最后的返回值，如果dp结果正好等于一半，那肯定返回0就行，但如果不是半，就是大的那部分减去小的那部分，结果应为(sum-dp[load])-dp[load]
494.目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
题目链接
个人题解
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<abs(target)) return 0;
if((target+sum)%2==1) return 0;
int bagsize=(target+sum)/2;
vector<vector<int>> dp(nums.size(),vector<int>(bagsize+1,0));
if(nums[0]<=bagsize) dp[0][nums[0]]=1;
dp[0][0]=1;
int zeroNum=0;
for(int i=0;i<nums.size();i++){
if(nums[i]==0) zeroNum++;
dp[i][0]=(int)pow(2.0,zeroNum);
}
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]+dp[i-1][j-nums[i]];
}
}
return dp[nums.size()-1][bagsize];
}
};
复杂度分析
- 时间复杂度：n*m
- 空间复杂度：m
解题思路
这道题的抽象程度感觉已经超出简单题的范畴了。
第一步，要求最后的结果等于target，将所有加法减法分开，设加法和为x，减法和就是sum-x,结果就是x-(sum-x)=target,化简为x = (target + sum) / 2，此时问题就转化为，用nums装满容量为x的背包，有几种方法。排除一下特殊情况，如果sum本身小于target，那么再怎么变正负号也没结果返回0，还有如果target+sum是奇数的话是无解的，因为这里x代表容量，显然容量不能有小数。
第二步，找dp关系，结果要求的是不同表达式的数目，因此dp的含义就是使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。
第三步，然后就要对dp进行初始化，首先重量为0时显然不放是一种方法，当只有一个物品时，重量恰好等于背包重量又是一种方法，还有一个特殊情况，如果有重量为0的物品，那么当背包重量为0时，可选的操作就是放和不放，也就是两种，如果有多个为0的物品，那就是多维的放和不放也就是2的0的次数次方。
第四步，找dp关系，对于每一个物品肯定只有放和不放两种选择
- 不放物品i：即背包容量为j，里面不放物品i，装满有dp[i - 1][j]中方法。
- 放物品i： 即：先空出物品i的容量，背包容量为（j - 物品i容量），放满背包有 dp[i - 1][j - 物品i容量] 种方法。
最后返回dp右下角的值即可
474.一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
题目链接
个人题解
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=0;i<strs.size();i++){
int zeroNum=0,oneNum=0;
for(char c:strs[i]){
if(c=='0') zeroNum++;
else oneNum++;
}
for(int j=m;j>=zeroNum;j--){
for(int k=n;k>=oneNum;k--){
dp[j][k]=max(dp[j][k],dp[j-zeroNum][k-oneNum]+1);
}
}
}
return dp[m][n];
}
};
复杂度分析
- 时间复杂度：kmn
- 空间复杂度：mn
解题思路
这道题上来给我吓住了，没怎么想就去看答案了，其实仔细想想也不是做不来。
我们可以先去掉一个维度来看，如果所有字符串中只有0，那么这道题就相当于一个背包大小为M，物品价值为字符串长度的01背包问题。
那么再加上一个维度，可以预见遍历物品这个维度肯定不会改变，需要改变的是第二层的遍历，这里将背包设置为mxn的大小，dp[i][j]表示最多有i个0和j个1的strs的最大子集的大小，初始化全为0。这里选择的是滚动数组的扩张，也就是将滚动数组转化为滚动二维数组（三维也可以其实）。
当一个物品进行遍历时，对于每一格如果该格的0,1数量都在当前字符串的可接受范围内（也就是m>strzeroNum,n>stroneNum），那么就可以放入该字符串，然后找放入后剩余部分放先前字符串的可能方法数，然后比较和不放这个字符串也就是原本该格的数组的数量，哪个大放哪个。由于是滚动数组扩张开的，滚动数组中是从后往前遍历，这个同理。最终dp递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
今日总结
dp好难，背包好难:(
今天啥也没做出来，感觉抽象题目这一步真的很难，根本想不通该怎么转化成背包问题。
0-1背包的应用这两总结下：
纯 0 - 1 背包 (opens new window)是求 给定背包容量 装满背包 的最大价值是多少。
416. 分割等和子集 (opens new window)是求 给定背包容量，能不能装满这个背包。
1049. 最后一块石头的重量 II (opens new window)是求 给定背包容量，尽可能装，最多能装多少
494. 目标和 (opens new window)是求 给定背包容量，装满背包有多少种方法。
本题是求 给定背包容量，装满背包最多有多少个物品。
原文地址：https://blog.csdn.net/qq_73823477/article/details/144329276
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！