Leetcode 刷题笔记(二十四) ——动态规划篇之背包问题：01背包

文章目录

系列文章目录

一、 数组类型解题方法一：二分法
二、数组类型解题方法二：双指针法
三、数组类型解题方法三：滑动窗口
四、数组类型解题方法四：模拟
五、链表篇之链表的基础操作和经典题目
六、哈希表篇之经典题目
七、字符串篇之经典题目
八、字符串篇之 KMP
九、解题方法：双指针
十、栈与队列篇之经典题目
十 一、栈与队列篇之 top-K 问题
十 二、二叉树篇之二叉树的前中后序遍历
十 三、二叉树篇之二叉树的层序遍历及相关题目
十 四、二叉树篇之二叉树的属性相关题目
十 五、 二叉树篇之二叉树的修改与构造
十 六、 二叉树篇之二叉搜索树的属性
十 七、二叉树篇之公共祖先问题
十 八、二叉树篇之二叉搜索树的修改与构造
十 九、回溯算法篇之组合问题
二 十、回溯算法篇之分割、子集、全排列问题
二十一、贪心算法篇之入门题目
二十二、贪心算法篇之进阶题目
二十三、动态规划篇之基础题目
更新中 … …

前言

一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包
刷题路线来自 ：代码随想录

题录

01背包问题

LintCode 链接
有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大?

题解：

/**
     * 状态 F(i,j): 前 i个物品放入大小为 j的背包中所获得的最大价值
     * 递推关系：当前背包放不下新增物品时 A(i-1) < j:
     *              F(i,j) = F(i-1,j)
     *     放得下时： F(i,j) = max{ (F(i-1, j), F(i-1, F(j - A(i-1))) + V(i - 1)}
     *     A(i-1):  新增物品的大小
     *     V(i-1):  新增物品的价格
     *     F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
     *     F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出j - A[i]的大小放
第i个商品
     *     初始状态：F(i,0) = F(0,j) = 0   第0行和第0列都为0，表示没有装物品时的价值都为0
     *     返回值：F(i,j)
     */publicclassSolution{publicintbackPackII(int m,int[]A,int[]V){int row =A.length;if(row ==0|| m ==0)return0;int[][] dp =newint[row +1][m +1];for(int i =1; i <= row; i++){// 遍历背包for(int j =1; j <= m; j++){// 遍历重量if(A[i -1]> j){// 新增物品质量大于当前背包，放不下
                    dp[i][j]= dp[i -1][j];}else{// 放得下，如果放入新物品要计算出背包剩余大小，看下剩余背包大小最多能装多少然后加上新增物品价格，和不放入新物品背包最大价格对比，取最大。最大价格都在上一层
                    dp[i][j]=Math.max(dp[i -1][j], dp[i -1][j -A[i -1]]+V[i -1]);}}}return dp[row][m];}}

空间优化：一维dp数组（滚动数组）

1. 寻找最大值时不用去上层 dp 数组中寻找，在原数组上修改，从后向前遍历，因为找背包剩余位置能放下的物品最多价值时需要向前找，且不能放入新物品。
2. 在遍历的时候在背包空间大于等于新物品的价值就可以，再向前遍历需要进行能不能放下物品的判断，而且也没有意义，放不下的话数组中的值也不会改变。

publicclassSolution{/**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */publicintbackPackII(int m,int[]A,int[]V){int row =A.length;if(m ==0)return0;int[] dp =newint[m +1];for(int i =0; i < row; i++){for(int j = m; j >=A[i]; j--){
                dp[j]=Math.max(dp[j], dp[j -A[i]]+V[i]);}}return dp[m];}}

416. 分割等和子集

Leetcode 链接

题解：
整个数组和为 sum，找到 sum / 2 的子数组即可
方法一： 回溯（结果超时）
如下两题几乎是一样的，可以用回溯法，解决如下两题
698.划分为k个相等的子集
473.火柴拼正方形

classSolution{boolean flag =false;int sumDfs =0;publicbooleancanPartition(int[] nums){int sum =0;for(int i =0; i < nums.length; i++){
            sum += nums[i];}if(sum %2==1)returnfalse;
        sum = sum /2;dfs(nums, sum,0);return flag;}publicvoiddfs(int[] nums,int sum,int start){if(sumDfs > sum){return;}if(sumDfs == sum){
            flag =true;return;}for(int i = start; i < nums.length; i++){
            sumDfs += nums[i];dfs(nums, sum, i +1);
            sumDfs -= nums[i];}}}

方法二：动态规划（这里直接用 一维dp数组）
背包大小为 sum / 2，物品为数组中的数值，物品的大小和价格都为 num[i]
dp[i] 可以直接看作大小为 i 的背包，装入物品的最大和。
返回值： dp[sum / 2] == sum / 2，sum / 2 大小的背包刚好装入 sum / 2 的物品最大和

classSolution{publicbooleancanPartition(int[] nums){int sum =0;for(int i =0; i < nums.length; i++){
            sum += nums[i];}if(sum %2==1)returnfalse;
        sum = sum /2;int[] dp =newint[sum +1];for(int i =0; i < nums.length; i++){for(int j = sum; j >= nums[i]; j--){
                dp[j]=Math.max(dp[j], dp[j - nums[i]]+ nums[i]);}}return dp[sum]== sum;}}

1049. 最后一块石头的重量 II

Leetcode 链接

1046. 最后一块石头的重量
将本体的任意石头改成最大的两块石头截然不同的两道题，使用优先级队列解决
题解：
难点：怎么就扯到 dp 了呢？看三叶大神的讲解
评论区大佬一语道破玄机：
因为每一次抵消，实际上都是[a, b, …]变成[a - b, …]或[b-a, …]的过程，最终也必然会得出类似 (b - a) - ( c - d) 这种计算式，展平得 -a + b - c + d = (b+d)-(a+c)这种计算式，b+d >= sum/2 >= a+c，需要做的就是找出a+c不大于sum/2时的最大值，经典背包问题。
dp[v] - (a + c) = b + d、 返回 (b + d) - (a + c)
返回值： sum - dp[v] - dp[v]; 前边的 sum - dp[v] 得到较大部分的和

classSolution{publicintlastStoneWeightII(int[] stones){int sum =0;for(int i : stones){
            sum += i;}int v = sum /2;int[] dp =newint[v +1];for(int i =0; i < stones.length; i++){for(int j = v; j >= stones[i]; j--){
                dp[j]=Math.max(dp[j], dp[j - stones[i]]+ stones[i]);}}// 注意返回值的含义return sum - dp[v]- dp[v];}}

494. 目标和

Leetcode 链接

题解：
由 bigSum - smallSum = target、bigSum + smallSum = sum
得 smallSum = (sum - target) / 2 (因为 smallSum < bigSum) 所以这里选 smallSum，而且由式子都为可知 为非负偶数。
多少种运算结果等于 target 的表达式数目由 bigSum - smallSum = target 这里的 bigSum 或 smallSum 的子组合数目决定。故本题相当于求：和为 bigSum 或 smallSum 的子数组最多组合数 可作为01 背包问题。
背包大小由 smallSum 决定，物品大小为 nums[i]。
dp[i][j]: 0 ~ i 个物品放入大小为 j 的背包的最大组合数目

classSolution{publicintfindTargetSumWays(int[] nums,int target){int row = nums.length;int sum =0;for(int i : nums){
            sum += i;}// 和都小于 target 了，返回 0if(sum - target <0)return0;if((sum - target)%2==1)return0;// smallSum 为非负偶数；int smallSum =(sum - target)/2;int[][] dp =newint[row +1][smallSum +1];// 因为刚好放下时，要在不要该物品的最大组合数上加上 1（只放该物品），所以dp[][0] 必须为1，dp[][0]都由 dp[0][0]得来
        dp[0][0]=1;for(int i =1; i <= row; i++){// 第二层背包大小从 0 开始，因为所以dp[][0] 必须为1for(int j =0; j <= smallSum; j++){if(j >= nums[i -1]){// 放得下时，放入前的最大组合数 dp[i - 1][j]，加上放入后的最大组合数 = 放入前背包大小 为j - num[i - 1]的最大组合数// num[i - 1]：0 号物品下标从 1 开始， 所以为新增物品下标为 i - 1// j - num[i - 1]：放入后背包还剩的大小
                    dp[i][j]= dp[i -1][j]+ dp[i -1][j - nums[i -1]];}else{// 放不下时
                    dp[i][j]= dp[i -1][j];}}}return dp[row][smallSum];}}

空间优化（一维滚动 dp 数组）：

classSolution{publicintfindTargetSumWays(int[] nums,int target){int row = nums.length;int sum =0;for(int i : nums){
            sum += i;}if(sum - target <0)return0;if((sum - target)%2==1)return0;int smallSum =(sum - target)/2;int[] dp =newint[smallSum +1];
        dp[0]=1;for(int i =0; i < row; i++){for(int j = smallSum; j >= nums[i]; j--){
                dp[j]= dp[j]+ dp[j - nums[i]];}}return dp[smallSum];}}

474. 一和零 （滚动二维dp）

Leetcode 链接

总结

1. 最大和类型的递推公式 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1])；降维后：dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
2. 求组合类型的递推公式 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]；降维后：dp[j] = dp[j] + dp[j - nums[i]];