Studying-代码随想录训练营day36| 1049.最后一块石头的重量II、494.目标和、474.一和零
第36天,动态规划part04💪(ง •_•)ง,0-1背包问题part02,编程语言:C++
目录
1049.最后一块石头的重量II
文档讲解:代码随想录最后一块石头的重量II
视频讲解:手撕最后一块石头的重量II
题目:力扣题目链接
学习:本题最重要的是理解题意,使得留下的石头的重量最小,因此我们应该尽可能的把石头分成重量相同的两堆,这就相当于是变成了两块石头,这样相撞得到的石头才会是最小的。因此本题就转化为了0-1背包问题,背包容量为sum / 2,我们要求的就是在容量为sum / 2的情况下能够装下的最大重量。
使用动规五部曲进行分析:
1.确定dp数组以及下标含义:本题与传统的0-1背包问题相同,可以采用一维滚动数组的方式,也可以采用二维数组的方式进行求解。在这里我们尝试使用二维数组进行求解。dp[i][j]:表示为从0 - i 的石头中取,容量为j的情况下,能够装下的最大价值(本题中石头重量与价值相等)。
vector<vector<int>> dp(stones.size(), vector<int>(target + 1, 0)); //dp[i][j]表示0-i个物品选择,容量j的情况下能够放下的最大价值
2.确定递推公式:根据0-1背包问题可以推出:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]),也即判断装下石头i和不装石头i谁的重量最大。
3.dp数组初始化:我们需要把第一列初始化为0,也即容量为0的情况下,装下的最大重量显然也是0。我们还需要把第一列中容量大于stones[0]的初始化为stones[0]。
4.确定遍历顺序:可以先遍历石头后遍历背包,也可以两者相反。
5.举例推导dp数组:实际上一维滚动数组就是压缩二维数组得到的。
代码:
//时间复杂度O(n*m)
//空间复杂度O(n*m)
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
//非常难想,要考虑两块石头相撞,实际上可以转化为两堆石头相撞
//0-1背包问题
//先求和,找出中间值
int sum = 0;
for (int i = 0; i < stones.size(); i++) {
sum += stones[i];
}
int target = sum/2;
//1.确定dp数组,以及下标的含义,我们采用二维dp数组的方式进行
vector<vector<int>> dp(stones.size(), vector<int>(target + 1, 0)); //dp[i][j]表示0-i个物品选择,容量j的情况下能够放下的最大价值
//2.确定递推公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i])
//3.初始化dp数组:对第一行进行初始化
for(int j = stones[0]; j <= target; j++) {
dp[0][j] = stones[0];
}
//4.确定遍历顺序:背包物品选一个先开始遍历
for(int i = 1; i < stones.size(); i++) {
for(int j = 1; 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[stones.size() - 1][target] - dp[stones.size() - 1][target];
}
};
代码:使用一维滚动数组的方式
//时间复杂度O(n*m)
//空间复杂度O(m)
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001, 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];
}
};
注意:实际上本题与上一篇博客中的416.分割等和子集是一样的,只不过是最后对dp[target]的处理方式不同。
494.目标和
文档讲解:代码随想录目标和
视频讲解:手撕目标和
题目: 力扣题目链接
学习:本题实际上也是一个组合问题,也即找到前面添加"+“号的组合,也即正数的组合。因此本题也可以采用回溯的方法,但回溯法时间复杂度较高。
我们通过找到正数的组合的角度出发,依照提议,我们需要找到加法总和 - 减法总和 = target。因此我们可以从找到运算结果等于target的不同表达式的数目,转变为在数组中找到能够凑成加法总和的组合数目(剩下的就是减法)。
我们假设加法总和为x,减法总和为y。则有 x + y = sum; x - y = target;由上述两式我们可以推导出y = sum - x;x = (sum + target) / 2。(注意:这里有两种特殊情况,首先由于x是由整数相加而来,因此也一定为整数,所以假如(sum + target)/ 2
因此本题又可以转变为0 - 1背包问题,把x作为背包的容量,求解数组中能够加起来等于x的组合数目。与前面的背包问题不同,本题求解的是能装到容量为j的组合数目。
从动态五部曲进行分析:
1. 确定dp数组以及下标的含义:本题我们采用一维滚动数组的方式(使用二维数组同样可以),dp[j]表示为数组中加和为j的最大组合总数。
2.确定递推公式:本题的递推公式不同于前面的背包问题。从dp[j]的含义出发,当我们在遍历数组中元素的时候,我们遍历到了nums[i] = 1,要组成dp[j]的方法有dp[j - 1]种,也就是有多少种组成dp[j - 1]的方法,就有多少种方法能组成dp[j]。同理当我们遍历到nums[i] = 2时,组成dp[j]的方法就有dp[i - 2]种。这是一个不断遍历,不断累加的过程,因此dp[j] += dp[j - nums[i]]。
3.dp数组初始化:我们需要初始化dp[0],dp[0]为数组中加和为0的种类,显然初始时数组为空集,空集也是一种种类(也可以理解为“+”的个数为0,数组中全为“-”能够打到target)。dp[0] = 1。
4.确定遍历顺序:一维滚动数组中需要先遍历物品,再遍历容量。
5.举例推导dp数组:
代码:
//时间复杂度O(n*m)
//空间复杂度O(m)
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
//动态规划方法
//求和
int sum = 0;
for(int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
sum += target;
if(sum % 2 == 1) return 0;
if(sum < 0) return 0;
int left = sum / 2;
//动归五部曲
//1.确定dp数组和下标的含义(我们这里使用一维滚动数组的方式)
vector<int> dp(left + 1); //dp[j]表示能够凑成j容量的最大方法
//2.确定递推公式,dp[j] += dp[j - nums[i]];
//3.初始化dp数组
dp[0] = 1; //0容量的最大方法,什么都不装都是一种方法
//4.确定遍历顺序
for(int i = 0; i < nums.size(); i++) {
for(int j = left; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[left];
}
};
474.一和零
文档讲解:代码随想录一和零
视频讲解:手撕一和零
题目:力扣题目链接
学习:本题是一个两个维度的0-1背包问题。是否能采用0-1背包的方法,最重要的是元素是否只能取用一次,是否有某个量的限制(重量,容量)。
在本题中对1和0的数量有限制,这其实就可以看作是两个背包,m,n分别是两个背包的容量。而strs数组里的元素就是物品,每个物品都是一个。
从动规五部曲出发:
1.确定dp数组以及下标的含义:两个背包我们可以采用二维dp数组(但实际上使用的是一维滚动数组的方法)。dp[i][j]表示最多有i个0,j个1的strs的最大子集的大小。
2.确定递推公式:dp[i][j]可以由前一个strs里的字符串推导出来。假设当前字符串由zeroNum个0,oneNum个1。dp[i][j]就可以是dp[i - zeroNum][j - oneNum] + 1。同时遍历的过程中我们取最大值。最后得到递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)。其实可以理解为,本题中每个字符串的价值都为1。
3.初始化dp数组:dp[0][0]表示0个1和0个0,显然子集个数为0,dp[0][0] = 0。
4.确定遍历顺序:本题中要注意的是,我们在遍历物品的时候,还需要统计一下它的0的个数,和1的个数。这才是该物品的主要元素。
5.举例推导dp数组:
代码:
//时间复杂度O(Kmn)
//空间复杂度O(mn)
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
//动态规划0-1背包:
//1.确定dp数组以及下标含义
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); //dp[i][j]表示最多i个0,j个1能包含的最大子集数。
//2.确定递推公式:dp[i][j] = max(dp[i][j], d[i - zeronum][j - onenum] + 1);
//3.初始化dp数组:dp[0][0] = 0; 表示最多0个0,0个1,显然包含0个最大子集数
//4.确定遍历吮吸
for(string str : strs) { //遍历背包
int zeronum = 0, onenum = 0; //记录每个字符串的0,1数量
for(char c : str) {
if(c == '0') zeronum++;
else onenum++;
}
for(int i = m; i >= zeronum; i--) { //遍历背包,实际上就是i一个背包,j一个背包,两个维度的背包
for(int j = n; j >= onenum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeronum][j - onenum] + 1);
}
}
}
return dp[m][n];
}
};
0-1背包总结
0-1背包的应用众多:
1.纯0-1背包问题:求给定背包容量装满背包的最大价值是多少?卡玛网46题目
2.416.分割等和子集:求给定背包容量,能不能装满背包?
3.1049.最后一块石头的重量II:求给定背包容量,尽可能装,最多能装多少?
4.494.目标和:求给定背包容量,装满背包有多少种方法。
5.474.一和零:求给定背包容量,装满背包最多有多少个物品。
原文地址:https://blog.csdn.net/yachihaoteng/article/details/140340986
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!