本文主要是介绍算法打卡day37|动态规划篇05| Leetcode1049.最后一块石头的重量II、494.目标和、474.一和零,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
算法题
Leetcode 1049.最后一块石头的重量II
题目链接:1049.最后一块石头的重量II
大佬视频讲解:最后一块石头的重量II视频讲解
个人思路
和昨天的分割等和子集有些相像,这道题也是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。
解法
动态规划
动规五部曲:
本题物品的重量为stones[i],物品的价值也为stones[i]。
对应着01背包里的物品重量weight[i]和 物品价值value[i]。
1.确定dp数组以及下标的含义
dp[j]表示容量为j的背包,最多可以背最大重量为dp[j]。
相对于 01背包,本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,所以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”
2.确定递推公式
01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
3.dp数组如何初始化
既然 dp[j]中的j表示容量,那么最大容量就是所有石头的重量和。
可以把石头遍历一遍,计算出石头总重量 然后除2,得到dp数组的大小。
初始化dp[j]:因为重量都不会是负数,所以dp[j]都初始化为0就可以了,这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]); 中dp[j]才不会初始值所覆盖。
4.确定遍历顺序
如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
5.举例推导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]。
class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//除2向下取整int[] dp = new int[target + 1];//初始化dp数组for (int i = 0; i < stones.length; i++) {for (int j = target; j >= stones[i]; j--) {//采用倒序dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - 2 * dp[target];}
}
时间复杂度:O(n^2);(嵌套for循环)
空间复杂度:O( n);(存储一个长度为n+1的dp数组)
二维数组版本
class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int s : stones) {sum += s;}int target = sum / 2;//初始化dp数组//dp[i][j]:可以放0-i物品,背包容量为j的情况下背包中的最大价值int[][] dp = new int[stones.length][target + 1];//dp[i][0]默认初始化为0//dp[0][j]取决于stones[0]for (int j = stones[0]; j <= target; j++) {dp[0][j] = stones[0];}for (int i = 1; i < stones.length; i++) {for (int j = 1; j <= target; j++) {if (j >= stones[i]) {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);} else {dp[i][j] = dp[i - 1][j];}}}return (sum - dp[stones.length - 1][target]) - dp[stones.length - 1][target];}
}
时间复杂度:O(n^2);(嵌套for循环)
空间复杂度:O( n^2);(dp二维数组)
Leetcode 494.目标和
题目链接:494.目标和
大佬视频讲解:目标和视频讲解
个人思路
以为可以回溯做出来,结果超时了...
解法
动态规划
动规五部曲:
这题转化为01背包问题的思路:
假设加法的总和为x,那么减法对应的总和就是sum - x。
所以要求的是 x - (sum - x) = target,x = (target + sum) / 2
此时问题就转化为,装满容量为x的背包,有几种方法。
这里的x,就是bagSize,也就是后面要求的背包容量。
因为(target + sum) / 2 在计算的过程中向下取整会有影响,比如sum=5时,target=2时就是无解的,同时如果 target的绝对值已经大于sum,那么也是没有方案的。这两种情况可以条件限制,减少遍历时间。
这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。本题则是装满有几种方法。其实这就是一个组合问题了。
1.确定dp数组以及下标的含义
dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法
2.确定递推公式
只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。
例如:dp[j],j 为5,
- 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
- 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
- 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包
- 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包
- 已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]的方法就是把 所有的 dp[j - nums[i]] 累加起来。所以求组合类问题的公式,都是类似这种:dp[j] += dp[j - nums[i]]
3.dp数组如何初始化
从递推公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是0的话,递推结果将都是0。
dp[j]其他下标对应的数值应该初始化为0,从递推公式也可以看出,dp[j]要保证是0的初始值,才能正确的由dp[j - nums[i]]推导出来。
4.确定遍历顺序
对于01背包问题一维dp的遍历,nums放在外循环,target在内循环,且内循环倒序。
5.举例推导dp数组
输入:nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下:
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int i = 0; i < nums.length; i++) sum += nums[i];//如果target的绝对值大于sum,那么是没有方案的if (Math.abs(target) > sum) return 0;//如果(target+sum)除以2的余数不为0,也是没有方案的if ((target + sum) % 2 == 1) return 0;int bagSize = (target + sum) / 2;int[] dp = new int[bagSize + 1];//初始化DP数组dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = bagSize; j >= nums[i]; j--) {//倒序dp[j] += dp[j - nums[i]];//组合问题递推公式}}return dp[bagSize];}
}
时间复杂度:O(n^2);(嵌套for循环)
空间复杂度:O( n);(存储一个长度为n+1的dp数组)
二维数组版本
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i = 0; i < nums.length; i++) {sum += nums[i];}// 注意nums[i] >= 0的题目条件,意味着sum也是所有nums[i]的绝对值之和// 这里保证了sum + target一定是大于等于零的,也就是left大于等于零(毕竟我们定义left大于right)if(sum < Math.abs(target)){return 0;}// 利用二元一次方程组将left用target和sum表示出来(替换掉right组合),详见代码随想录对此题的分析// 如果所求的left数组和为小数,则作为整数数组的nums里的任何元素自然是没有办法凑出这个小数的if((sum + target) % 2 != 0) {return 0;}int left = (sum + target) / 2;// dp[i][j]:遍历到数组第i个数时, left为j时的能装满背包的方法总数int[][] dp = new int[nums.length][left + 1];// 初始化最上行(dp[0][j]),当nums[0] == j时(注意nums[0]和j都一定是大于等于零的,因此不需要判断等于-j时的情况),有唯一一种取法可取到j,dp[0][j]此时等于1// 其他情况dp[0][j] = 0// java整数数组默认初始值为0if (nums[0] <= left) {dp[0][nums[0]] = 1;}// 初始化最左列(dp[i][0])// 当从nums数组的索引0到i的部分有n个0时(n > 0),每个0可以取+/-,因此有2的n次方中可以取到j = 0的方案// n = 0说明当前遍历到的数组部分没有0全为正数,因此只有一种方案可以取到j = 0(就是所有数都不取)int numZeros = 0;for(int i = 0; i < nums.length; i++) {if(nums[i] == 0) {numZeros++;}dp[i][0] = (int) Math.pow(2, numZeros);}// 递推公式分析:// 当nums[i] > j时,这时候nums[i]一定不能取,所以是dp[i - 1][j]种方案数// nums[i] <= j时,num[i]可取可不取,因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]// 由递推公式可知,先遍历i或j都可for(int i = 1; i < nums.length; i++) {for(int j = 1; j <= left; 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.length - 1][left];}
}
时间复杂度:O(n^2);(嵌套for循环)
空间复杂度:O( n^2);(dp二维数组)
Leetcode 474.一和零
题目链接:474.一和零
大佬视频讲解:一和零视频讲解
个人思路
没思路...
解法
动态规划
本题中strs 数组里的元素就是物品,每个物品都是一个!而m 和 n相当于是一个背包,两个维度的背包。转换为01背包问题,只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。
动规五部曲
1.确定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背包! 只不过物品的重量有了两个维度而已。
3.dp数组如何初始化
因为物品价值不会是负数,dp数组初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。
4.确定遍历顺序
01背包一维数组解法中,一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。
5.举例推导dp数组
以输入:["10","0001","111001","1","0"],m = 3,n = 3为例;最后dp数组的状态如下所示:
class Solution {public int findMaxForm(String[] strs, int m, int n) {//dp[i][j]表示i个0和j个1时的最大子集int[][] dp = new int[m + 1][n + 1];int oneNum, zeroNum;for (String str : strs) {oneNum = 0;zeroNum = 0;for (char ch : str.toCharArray()) {if (ch == '0') {zeroNum++;} else {oneNum++;}}//倒序遍历for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}
时间复杂度:O(kmn);(k 为strs的长度)
空间复杂度:O( n^2);(dp二维数组)
以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网
这篇关于算法打卡day37|动态规划篇05| Leetcode1049.最后一块石头的重量II、494.目标和、474.一和零的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!