前言 : 动规五部曲
1.明白dp数组的含义
2.明白递推公式的含义
3.初始化dp数组
4.注意dp数组的遍历顺序
5.打印dp数组排错
LeetCode T1049 最后一块石头的重量II
题目链接:1049. 最后一块石头的重量 II - 力扣（LeetCode）
题目思路:
这题我们仍然采用动规五部曲来写,这题和昨天的那一道分割等和子集类似,我们先对数组求和得到sum,然后取其的一半+1作为dp数组的大小,最后我们只需要求得sum/2作为容量的背包能装的最大容量,用sum减去两倍的dp[sum/2]即可,有人问为什么这样做,我举个例子
为什么要减去两倍的dp[sum/2]呢,其实就是求两边到中间的距离的,因为是左边和右边所以减了两次
想明白了这个,我们开始使用动规五部曲来操作了
1.明白dp数组的含义
dp[j]的含义仍然是j容量的背包能装的最大价值,这里的最大价值也就是最大重量了
2.明白递推公式的含义
这里的stones的价值和重量是相等的
dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[j])
有人始终不明白这里的dp[j]后面为什么求dp[j]和dp[j-stones[i]]+stones[j]的最大值,为啥跟自己求最大值,其实这里后面的dp[j]还保存了上一层的dp[j]的大小,因为没有被更新过,所以其实不是跟自己比
3.初始化dp数组
这里因为石头的重量都是大于0的,我们全部初始化为0即可
4.注意dp数组的遍历顺序
先遍历物品,后遍历背包即可,不明白的看我的上一篇博客
代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树-CSDN博客
5.打印dp数组排错
如果遇到所求不符合了,可以去idea打印出数组来查看,这里建议使用二维数组的方式查看,更加直观
题目代码:(一维数组版本)
class Solution { public int lastStoneWeightII(int[] stones) { int sum = 0; for(int i: stones){ sum+=i; } int target = sum/2; int[] dp = new int[target+1]; 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-dp[target]-dp[target]; } }
题目代码:(二维数组版本)
class Solution { public int lastStoneWeightII(int[] stones) { int sum = 0; for(int i: stones){ sum+=i; } int target = sum/2; int[][] dp = new int[stones.length][target+1]; for(int i = stones[0];i<=target;i++){ dp[0][i] = stones[0]; } for(int i = 1;i<stones.length;i++){ for(int j = 1;j<=target;j++){ //不放 if(j<stones[i]){ dp[i][j] = dp[i-1][j]; } //放 else{ dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]); } } } return sum-dp[stones.length-1][target]*2; } }
LeetCode T494 目标和
题目思路:
我们也将数组按正负号划分为两个阵营,此时我们是不是只需要求一边的结果,另一边自然而然就确定了,所以这道题我们就有这样两个表达式
left//表示正的阵营 right//表示负的阵营 left + right = sum left - right = target left = (target+sum)/2
这里我们就知道了背包的容量为left的大小对应的表达式
这里如果我们的所求target>sum或者小于-sum都是不可能达成的
还有如果遇见target和sum的和为奇数也是不可能的,直接返回0,这是因为奇数/2是向下取整的,举个例子:
假如我的nums是[1,1,1,1,1],要求得到2
这里left明显等于3
而三个1加上两个-1得到是1,并不符合题意,实际上这个选择是无解的
接下来我们继续按照动规五部曲来走一遍
1.明白dp数组的含义
这里的dp[j]表示,容量为j的背包装满有多少种方法
2.明白递推公式的含义
dp[j] +=dp[j-nums[i]]
因为这里要求方法有多少种,举个例子
dp[5] = dp[4] + 1 其实和斐波那契数列和爬楼梯有点类似,可以相成到达5的方法数就是4的方法数+后面nums[j-nums[i]]的方法数
- 已经有一个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],就是把他们都累加起来
3.初始化dp数组
这里初始化dp[0] = 1,我们不要根据字面关系去理解,直接带入上面的公式理解
left = (target+sum)/2,此时left = 0,这就是一种方法
所以dp[0]要初始化为1而不是0,因为后面都得靠dp[0]推导出来,如果它为0后面的结果都是0
4.注意dp数组的遍历顺序
先遍历物品,后遍历背包
5.打印dp数组排错
题目代码:
class Solution { public int findTargetSumWays(int[] nums, int target) { int sum = 0; for(int i:nums){ sum += i; } if(target>sum || target<-sum){ return 0; } if((target + sum) % 2 == 1){ return 0; } int bagSize = (target+sum)/2; int[] dp = new int[bagSize+1]; 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]; } }
LeetCode T474 一和零
题目思路:
这道题也是一个背包问题,虽然有点抽象,下面我们开始用动规五部曲来分析
1.明白dp数组的含义
这里的dp数组的含义就是m个0和n个1能包含的最大子集,也就是能装下m个0和n个1的背包能存放的最大物品数
2.明白递推公式的含义
我们从最初的0-1背包开始递推
dp[j] = Math.max(dp[j],dp[j - weight[i]]+value[i])
这里我们的重量其实就是i和j的个数,我们使用x代表这个物品中的'0'的个数,y代表1的个数
那么此时就转换成了
dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1)
因为此时如果能放进去,也就是加了1个物品
3.初始化dp数组
此时dp[0][0] 很轻易就能知道是0,为了我们的递推公式能顺利的覆盖结果,其他的也初始化为0
4.注意dp数组的遍历顺序
和之前一样,先遍历物品,再遍历背包即可
5.打印dp数组排错
题目代码:
class Solution { public int findMaxForm(String[] strs, int m, int n) { //dp数组含义 int[][] dp = new int[m+1][n+1]; //初始化,全为0 for(String s:strs){ int x = 0,y = 0; for(char c:s.toCharArray()){ if(c == '0'){ x++; }else{ y++; } } for(int i = m;i>=x;i--){ for(int j = n;j>=y;j--){ dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1); } } } return dp[m][n]; } }
