本文主要是介绍代码随想录Day 36|滑铁卢了,leetcode题目:1049.最后一块石头的重量、494.目标和、474.一和零,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
提示:DDU,供自己复习使用。欢迎大家前来讨论~
文章目录
- 动态规划
- 一、题目
- 题目一:1049.最后一块石头的重量II
- 解题思路:
- 题目二:494.目标和
- 动态规划 (二维dp数组)
- #动态规划 (一维dp数组)
- 题目三: 474.一和零
- 解题思路:
- 总结
动态规划
有点难了,之前差的有点多,找时间补
一、题目
题目一:1049.最后一块石头的重量II
leetcode题目链接
解题思路:
本题:
想象一下,你有一堆苹果,你要把它们分成两堆,使得这两堆苹果的总数尽可能接近。但是,你每次只能从这堆苹果里拿出两个来,然后放一个苹果回去,这个新放回去的苹果是那两个苹果的重量差。这个过程重复进行,直到你不能再拿出两个苹果为止。
现在,我们一步步来看这个过程:
-
开始:你有一堆苹果,比如【31, 26, 33, 21, 40】。
-
第一次比较:你拿出最重的两个苹果,40和21,它们的重量差是19,你把这个重量差19放回去,苹果堆变成了【19, 26, 31, 33】。
-
第二次比较:你再拿出两个苹果,比如31和19,它们的重量差是12,你把这个重量差12放回去,苹果堆变成了【12, 26, 33】。
-
第三次比较:你继续拿出两个苹果,比如33和12,它们的重量差是21,你把这个重量差21放回去,苹果堆变成了【21, 26】。
-
第四次比较:现在你只有两个苹果了,你拿出26和21,它们的重量差是5,你把这个重量差5放回去,苹果堆变成了。
-
结束:现在你只剩下一个苹果了,这个过程就结束了。这个最后的苹果重量5,就是两堆苹果重量差的最小值。
-
分组:回头看,你实际上是在尝试找到两堆苹果,一堆是【31, 26, 21】,另一堆是【40, 33】。这两堆苹果的总重量分别是78和74,它们的差值就是4,这是你通过比较苹果重量差得到的结果。
-
找平衡:这个过程就像是在找两堆苹果,让它们的总重量尽可能接近。这就像是你有一个天平,你想要两边放的苹果重量差不多,这样天平才能平衡。
所以,通过两两比较苹果的重量差,你实际上是在尝试找到两堆苹果,让它们的总重量尽可能接近。这个过程就像是在解决一个找平衡的问题,也就是我们说的01背包问题。这个问题的关键是找到一种方法,让两堆苹果的总重量尽可能接近,这样天平才能平衡。
本题物品的重量为stones[i],物品的价值也为stones[i]。
对应着01背包里的物品重量weight[i]和 物品价值value[i]。
接下来进行动规五步曲:
- 确定dp数组以及下标的含义
dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。
可以回忆一下01背包中,dp[j]的含义,容量为j的背包,最多可以装的价值为 dp[j]。
相对于 01背包,本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”
- 确定递推公式
01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
- dp数组如何初始化
既然 dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。
因为提示中给出1 <= stones.length <= 30,1 <= stones[i] <= 1000,所以最大重量就是30 * 1000 。
而我们要求的target其实只是最大重量的一半,所以dp数组开到15000大小就可以了。
当然也可以把石头遍历一遍,计算出石头总重量 然后除2,得到dp数组的大小。
这里就直接用15000了。
接下来就是如何初始化dp[j]呢,因为重量都不会是负数,所以dp[j]都初始化为0就可以了,这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。
代码为:
vector<int> dp(15001, 0);
- 确定遍历顺序
如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
代码如下:
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]);}
}
- 举例推导dp数组
举例,输入:[2,4,1,1],此时target = (2 + 4 + 1 + 1)/2 = 4 ,dp数组状态图如下:
最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。
在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
以上分析完毕,C++代码如下:
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];}
};
- 时间复杂度:O(m × n) , m是石头总重量(准确的说是总重量的一半),n为石头块数
- 空间复杂度:O(m
题目二:494.目标和
动态规划 (二维dp数组)
假设加法的总和为x,那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为,装满容量为x的背包,有几种方法。
这里的x,就是bagSize,也就是我们后面要求的背包容量。
大家看到(target + sum) / 2
应该担心计算的过程中向下取整有没有影响。
这么担心就对了,例如sum是5,target是2 的话其实就是无解的,所以:
(C++代码中,输入的S 就是题目描述的 target)
if ((target + sum) % 2 == 1) return 0; // 此时没有方案
同时如果target 的绝对值已经大于sum,那么也是没有方案的。
if (abs(target) > sum) return 0; // 此时没有方案
因为每个物品(题目中的1)只用一次!
这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
- 确定dp数组以及下标的含义
先用 二维 dp数组求解本题,dp[i][j]:使用 下标为[0, i]的nums[i]能够凑满j(包括j)这么大容量的包,有dp[i][j]种方法。
- 确定递推公式
先手动推导一下,这个二维数组里面的数值。
先只考虑物品0,如图:
(这里的所有物品,都是题目中的数字1)。
装满背包容量为0 的方法个数是1,即 放0件物品。
装满背包容量为1 的方法个数是1,即 放物品0。
装满背包容量为2 的方法个数是0,目前没有办法能装满容量为2的背包。
接下来 考虑 物品0 和 物品1,如图:
装满背包容量为0 的方法个数是1,即 放0件物品。
装满背包容量为1 的方法个数是2,即 放物品0 或者 放物品1。
装满背包容量为2 的方法个数是1,即 放物品0 和 放物品1。
其他容量都不能装满,所以方法是0。
接下来 考虑 物品0 、物品1 和 物品2 ,如图:
装满背包容量为0 的方法个数是1,即 放0件物品。
装满背包容量为1 的方法个数是3,即 放物品0 或者 放物品1 或者 放物品2。
装满背包容量为2 的方法个数是3,即 放物品0 和 放物品1、放物品0 和 物品 2、 放物品1 和 物品2。
装满背包容量为3的方法个数是1,即 放物品0 和 物品1 和 物品2。
通过以上举例,我们来看 dp[2][2] 可以有哪些方向推出来。
如图红色部分:
dp[2][2] = 3,即 放物品0 和 放物品1、放物品0 和 物品 2、放物品1 和 物品2, 如图所示,三种方法:
容量为2 的背包,如果不放 物品2 有几种方法呢?
有 dp[1][2] 种方法,即 背包容量为2,只考虑物品0 和 物品1 ,有 dp[1][2] 种方法,如图:
容量为2 的背包, 如果放 物品2 有几种方法呢?
首先 要在背包里 先把物品2的容量空出来, 装满 刨除物品2容量 的背包 有几种方法呢?
刨除物品2容量后的背包容量为 1。
此时装满背包容量为1 有 dp[1][1] 种方法,即: 不放物品2,背包容量为1,只考虑物品 0 和 物品 1,有 dp[1][1] 种方法。
如图:
有录友可能疑惑,这里计算的是放满 容量为2的背包 有几种方法,那物品2去哪了?
在上面图中,你把物品2补上就好,同样是两种方法。
dp[2][2] = 容量为2的背包不放物品2有几种方法 + 容量为2的背包不放物品2有几种方法
所以 dp[2][2] = dp[1][2] + dp[1][1] ,如图:
以上过程,抽象化如下:
- 不放物品i:即背包容量为j,里面不放物品i,装满有dp[i - 1][j]中方法。
- 放物品i: 即:先空出物品i的容量,背包容量为(j - 物品i容量),放满背包有 dp[i - 1][j - 物品i容量] 种方法。
本题中,物品i的容量是nums[i],价值也是nums[i]。
递推公式:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
考到这个递推公式,我们应该注意到,j - nums[i]
作为数组下标,如果 j - nums[i]
小于零呢?
说明背包容量装不下 物品i,所以此时装满背包的方法值 等于 不放物品i的装满背包的方法,即:dp[i][j] = dp[i - 1][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]];
1
2
- dp数组如何初始化
先明确递推的方向,如图,求解 dp[2][2] 是由 上方和左上方推出。
那么二维数组的最上行 和 最左列一定要初始化,这是递推公式推导的基础,如图红色部分:
关于dp[0][0]的值,在上面的递推公式讲解中已经讲过,装满背包容量为0 的方法数量是1,即 放0件物品。
那么最上行dp[0][j] 如何初始化呢?
dp[0][j]:只放物品0, 把容量为j的背包填满有几种方法。
只有背包容量为 物品0 的容量的时候,方法为1,正好装满。
其他情况下,要不是装不满,要不是装不下。
所以初始化:dp[0][nums[0]] = 1 ,其他均为0 。
表格最左列也要初始化,dp[i][0] : 背包容量为0, 放物品0 到 物品i,装满有几种方法。
都是有一种方法,就是放0件物品。
即 dp[i][0] = 1
- 确定遍历顺序
在明确递推方向时,我们知道 当前值 是由上方和左上方推出。
那么我们的遍历顺序一定是 从上到下,从左到右。
因为只有这样,我们才能基于之前的数值做推导。
例如下图,如果上方没数值,左上方没数值,就无法推出 dp[2][2]。
那么是先 从上到下 ,再从左到右遍历,例如这样:
for (int i = 1; i < nums.size(); i++) { // 行,遍历物品for (int j = 0; j <= bagSize; j++) { // 列,遍历背包}
}
还是先 从左到右,再从上到下呢,例如这样:
for (int j = 0; j <= bagSize; j++) { // 列,遍历背包for (int i = 1; i < nums.size(); i++) { // 行,遍历物品}
}
其实以上两种遍历都可以! (但仅针对二维DP数组是这样的)
这一点我在 01背包理论基础 (opens new window)中的 遍历顺序部分讲过。
这里我再画图讲一下,以求dp[2][2]为例,当先从上到下,再从左到右遍历,矩阵是这样:
当先从左到右,再从上到下遍历,矩阵是这样:
这里大家可以看出,无论是以上哪种遍历,都不影响 dp[2][2]的求值,用来 推导 dp[2][2] 的数值都在。
- 举例推导dp数组
输入:nums: [1, 1, 1, 1, 1], target: 3
bagSize = (target + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下:
这么大的矩阵,我们是可以自己手动模拟出来的。
在模拟的过程中,既可以帮我们寻找规律,也可以帮我们验证 递推公式加遍历顺序是不是按照我们想象的结果推进的。
最后二维dp数组的C++代码如下:
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 ((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 numZero = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) numZero++;dp[i][0] = (int) pow(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] + dp[i - 1][j - nums[i]];}}return dp[nums.size() - 1][bagSize];}
};
#动态规划 (一维dp数组)
将二维dp数组压缩成一维dp数组,重复利用每一行,就是将二维数组压缩成一行。
dp[i][j] 去掉 行的维度,即 dp[j],表示:填满j(包括j)这么大容积的包,有dp[j]种方法。
- 确定递推公式
二维DP数组递推公式: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
去掉维度i 之后,递推公式:dp[j] = dp[j] + dp[j - nums[i]]
,即:dp[j] += dp[j - nums[i]]
这个公式在后面在讲解背包解决排列组合问题的时候还会用到!
- dp数组如何初始化
在上面 二维dp数组中,我们讲解过 dp[0][0] 初始为1,这里dp[0] 同样初始为1 ,即装满背包为0的方法有一种,放0件物品。
- 确定遍历顺序
在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中,我们系统讲过对于01背包问题一维dp的遍历。
遍历物品放在外循环,遍历背包在内循环,且内循环倒序(为了保证物品只使用一次)。
- 举例推导dp数组
输入:nums: [1, 1, 1, 1, 1], target: 3
bagSize = (target + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下:
大家可以和 二维dp数组的打印结果做一下对比。
一维DP的C++代码如下:
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 ((target + sum) % 2 == 1) 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];}
};
- 时间复杂度:O(n × m),n为正数个数,m为背包容量
- 空间复杂度:O(m),m为背包容
题目三: 474.一和零
没太明白,期待二刷
解题思路:
本题中strs 数组里的元素就是物品,每个物品都是一个!
而m 和 n相当于是一个背包,两个维度的背包。
理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。
但本题其实是01背包问题!
只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。
开始动规五部曲:
- 确定dp数组(dp table)以及下标的含义
dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中,取dp[i][j]的最大值。
所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。
这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。
-
dp数组如何初始化
因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。
-
确定遍历顺序
01背包一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!
那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。
代码如下:
for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '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);}}
}
5.举例推导dp数组
以输入:[“10”,“0001”,“111001”,“1”,“0”],m = 3,n = 3为例
最后dp数组的状态如下所示:
以上动规五部曲分析完毕,C++代码如下:
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '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];}
};
- 时间复杂度: O(kmn),k 为strs的长度
- 空间复杂度: O(mn)
C++: 使用三维数组的版本
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int num_of_str = strs.size();vector<vector<vector<int>>> dp(num_of_str, vector<vector<int>>(m + 1,vector<int>(n + 1, 0)));/* dp[i][j][k] represents, if choosing items among strs[0] to strs[i] to form a subset, what is the maximum size of this subset such that there are no more than m 0's and n 1's in this subset. Each entry of dp[i][j][k] is initialized with 0transition formula:using x[i] to indicates the number of 0's in strs[i]using y[i] to indicates the number of 1's in strs[i]dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j - x[i]][k - y[i]] + 1)*/// num_of_zeros records the number of 0's for each str// num_of_ones records the number of 1's for each str// find the number of 0's and the number of 1's for each str in strsvector<int> num_of_zeros;vector<int> num_of_ones;for (auto& str : strs){int count_of_zero = 0;int count_of_one = 0;for (char &c : str){if(c == '0') count_of_zero ++;else count_of_one ++;}num_of_zeros.push_back(count_of_zero);num_of_ones.push_back(count_of_one);}// num_of_zeros[0] indicates the number of 0's for str[0]// num_of_ones[0] indiates the number of 1's for str[1]// initialize the 1st plane of dp[i][j][k], i.e., dp[0][j][k]// if num_of_zeros[0] > m or num_of_ones[0] > n, no need to further initialize dp[0][j][k], // because they have been intialized to 0 previouslyif(num_of_zeros[0] <= m && num_of_ones[0] <= n){// for j < num_of_zeros[0] or k < num_of_ones[0], dp[0][j][k] = 0for(int j = num_of_zeros[0]; j <= m; j++){for(int k = num_of_ones[0]; k <= n; k++){dp[0][j][k] = 1;}}}/* if j - num_of_zeros[i] >= 0 and k - num_of_ones[i] >= 0:dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j - num_of_zeros[i]][k - num_of_ones[i]] + 1) else:dp[i][j][k] = dp[i-1][j][k]*/for (int i = 1; i < num_of_str; i++){int count_of_zeros = num_of_zeros[i];int count_of_ones = num_of_ones[i]; for (int j = 0; j <= m; j++){for (int k = 0; k <= n; k++){if( j < count_of_zeros || k < count_of_ones){dp[i][j][k] = dp[i-1][j][k];}else{dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j - count_of_zeros][k - count_of_ones] + 1);}}}}return dp[num_of_str-1][m][n];}
};
总结
- 今天学习的内容,学的很泛,没太明白
- 坚持进度吧
这篇关于代码随想录Day 36|滑铁卢了,leetcode题目:1049.最后一块石头的重量、494.目标和、474.一和零的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!