Day42——Dp专题

朴灿烈づ我的快乐病毒、 2024-03-31 16:54 66阅读 0赞

#### 文章目录 ####

*   *  五、多重背包
     *  六、背包问题总结
     *   *   *  动规五部曲
             *  背包递推公式
             *  遍历顺序
         *  18.打家劫舍
         *  19.打家劫舍II
         *  20.打家劫舍 III（dfs+缓存/树形DP）

--------------------

### 五、多重背包 ###

对于多重背包，我在力扣上还没发现对应的题目，所以这里就做一下简单介绍，大家大概了解一下。

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的， 为什么和01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

问背包能背的物品最大价值是多少？

和如下情况有区别么？

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。

**多重背包就是将01背包的数量拆开**

*  01背包每个数量都是一个，多重背包数量可以为多个

**Code**

public void testMultiPack1(){
        
        // 版本一：改变物品数量为01背包格式
        List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
        List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
        List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));
        int bagWeight = 10;
    
        for (int i = 0; i < nums.size(); i++) {
        
            while (nums.get(i) > 1) {
         // 把物品展开为i
                weight.add(weight.get(i));
                value.add(value.get(i));
                nums.set(i, nums.get(i) - 1);
            }
        }
    
        int[] dp = new int[bagWeight + 1];
        for(int i = 0; i < weight.size(); i++) {
         // 遍历物品
            for(int j = bagWeight; j >= weight.get(i); j--) {
         // 遍历背包容量
                dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
            }
            System.out.println(Arrays.toString(dp));
        }
    }
    
    public void testMultiPack2(){
        
        // 版本二：改变遍历个数
        int[] weight = new int[] {
        1, 3, 4};
        int[] value = new int[] {
        15, 20, 30};
        int[] nums = new int[] {
        2, 3, 2};
        int bagWeight = 10;
    
        int[] dp = new int[bagWeight + 1];
        for(int i = 0; i < weight.length; i++) {
         // 遍历物品
            for(int j = bagWeight; j >= weight[i]; j--) {
         // 遍历背包容量
                // 以上为01背包，然后加一个遍历个数
                for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {
         // 遍历个数
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
                System.out.println(Arrays.toString(dp));
            }
        }
    }

### 六、背包问题总结 ###

关于这几种常见的背包，其关系如下：

![image-20221209111603255][]

##### 动规五部曲 #####

1.  **确定dp数组（dp table）以及下标的含义**
2.  **确定递推公式**
3.  **dp数组如何初始化**
4.  **确定遍历顺序**
5.  **举例推导dp数组**

##### 背包递推公式 #####

问能否能装满背包（或者最多装多少）：`dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])`; ，对应题目如下：

*  [动态规划：416.分割等和子集][416.]
 *  [动态规划：1049.最后一块石头的重量 II][1049._ II]

问装满背包有几种方法：`dp[j] += dp[j - nums[i]`\] ，对应题目如下：

*  [动态规划：494.目标和][494.]
 *  [动态规划：518. 零钱兑换 II][518. _ II]
 *  [动态规划：377.组合总和Ⅳ][377.]
 *  [动态规划：70. 爬楼梯进阶版（完全背包][70.]

问背包装满最大价值：`dp[j] = max(dp[j], dp[j - weight[i]] + value[i])`; ，对应题目如下：

*  [动态规划：474.一和零][474.]

问装满背包所有物品的最小个数：`dp[j] = min(dp[j - coins[i]] + 1, dp[j])`; ，对应题目如下：

*  [动态规划：322.零钱兑换][322.]
 *  [动态规划：279.完全平方数][279.]

##### 遍历顺序 #####

**01背包**

*  **二维数组**遍历顺序先遍历物品还是先遍历背包都可以，遍历背包**正序遍历**
 *  **一维数组**必须先遍历物品之后遍历背包，遍历背包必须**倒叙遍历**

**完全背包**

*  如果求组合数就是外层for循环遍历物品，内层for遍历背包；如果求排列数就是外层for遍历背包，内层for循环遍历物品。
 *  单纯的完全背包问题，遍历顺序先遍历物品还是先遍历背包都可以，遍历背包**正序遍历**

#### 18.打家劫舍 ####

[力扣题目链接][Link 1]

**思路**

**动规五部曲**

*  **确定dp数组以及下标的含义**

dp\[i\]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp\[i\]。

*  **确定递推公式**

决定dp\[i\]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp\[i\] = dp\[i - 2\] + nums\[i\] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp\[i-2\] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp\[i\] = dp\[i - 1\]，即考虑i-1房，（**注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点**）

然后dp\[i\]取最大值，即dp\[i\] = max(dp\[i - 2\] + nums\[i\], dp\[i - 1\]);

*  **dp数组如何初始化**

从递推公式dp\[i\] = max(dp\[i - 2\] + nums\[i\], dp\[i - 1\]);可以看出，递推公式的基础就是dp\[0\] 和 dp\[1\]

从dp\[i\]的定义上来讲，dp\[0\] 一定是 nums\[0\]，dp\[1\]就是nums\[0\]和nums\[1\]的最大值即：dp\[1\] = max(nums\[0\], nums\[1\]);

dp[0] = nums[0];
    		dp[1] = Math.max(dp[0], nums[1]);

*  **确定遍历顺序**

dp\[i\] 是根据dp\[i - 2\] 和 dp\[i - 1\] 推导出来的，那么一定是从前到后遍历！

for (int i = 2; i < nums.length; i++) {
        
    			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    		}

*  **举例推导dp数组**

![image-20221209122152699][]

红框dp\[nums.size() - 1\]为结果。

**Code**

// 动态规划
    class Solution {
        
    	public int rob(int[] nums) {
        
    		if (nums == null || nums.length == 0) return 0;
    		if (nums.length == 1) return nums[0];
    
    		int[] dp = new int[nums.length];
    		dp[0] = nums[0];
    		dp[1] = Math.max(dp[0], nums[1]);
    		for (int i = 2; i < nums.length; i++) {
        
    			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    		}
    
    		return dp[nums.length - 1];
    	}
    }

#### 19.打家劫舍II ####

[力扣题目链接][Link 2]

**思路**

*  情况一：考虑不包含首尾元素
 *  情况二：考虑包含首元素，不包含尾元素
 *  情况三：考虑包含尾元素，不包含首元素

**而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了，套用打家劫舍Ⅰ**。

class Solution {
        
        public int rob(int[] nums) {
        
            int n = nums.length;
            if(nums == null || n == 0){
        
                return 0;
            }
            if(n == 1){
        
                return nums[0];
            }
    
            int res2 = fun(nums, 0, n - 2);// 情况2（含头不含尾）
            int res3 = fun(nums, 1, n - 1);// 情况3（含尾不含头）
            return Math.max(res3, res2);
        }
    
        // 打家劫舍I的处理方式
        public int fun(int[] nums, int l, int r){
        
            if(l == r) return nums[l];
            int[] dp = new int[nums.length + 10];
            dp[l] = nums[l];
            dp[l + 1] = Math.max(nums[l], nums[l + 1]);
            for(int i = l + 2; i <= r; i ++){
        
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
            }
            return dp[r];
        }
    }

#### 20.打家劫舍 III（dfs+缓存/树形DP） ####

题目链接：[337. 打家劫舍 III - 力扣（LeetCode）][Link 2]

**依旧是打家劫舍I的思考方式，对于每一个根节点有偷和不偷两种情况：**

*  偷根节点：那么它的左右儿子节点就不能偷了，那我们递归去偷它的左右子孙
 *  不偷根节点：那么它的左右儿子节点就能偷了，那我们递归去偷它的左右儿子即可

**思路**

**递归三部曲和动规五部曲**

*  **确定递归函数的参数和返回值**

所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

所以本题dp数组就是一个长度为2的数组！

*  **确定终止条件**

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

*  **确定遍历顺序**

首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。

通过递归左节点，得到左节点偷与不偷的金钱。

通过递归右节点，得到右节点偷与不偷的金钱。

*  **确定单层递归的逻辑**

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left\[0\] + right\[0\]; （**如果对下标含义不理解就在回顾一下dp数组的含义**）

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left\[0\], left\[1\]) + max(right\[0\], right\[1\]);

最后当前节点的状态就是\{val2, val1\}; 即：\{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱\}

*  **举例推导dp数组**

![image-20221209142200554][]

**最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱**。

每一个节点是否选取，**取决于它的左右子树是否选取**。

假设`dp[0]`：表示当前节点不选，`dp[1]`：表示选取当前节点

`dpl[] dpr[]`分别表示左右子树节点是否选取（`dpl[1] dpr[1]`）和不选取（`dpl[0] dpr[0]`）的最大值。

那么状态转移方程：

*  `dp[0]`：`dp[0] = max(dpl[0], dpl[1]) + max(dpr[0], dpr[1])`
 *  `dp[1]`：`dp[1] = root.val + dpl[0] + dpr[0]`

最终答案：`max(f[0], f[1])`，选根和不选根的最大情况

**之所以采用有序遍历是因为，根节点的情况取决于左右子树的情况，为此先要递归计算出左右子树！**

**Code**

class Solution {
        
        public int rob(TreeNode root) {
        
            int[] dp = new int[2];
            dp = dfs(root);
            return Math.max(dp[0], dp[1]);
        }
        
        public int[] dfs(TreeNode root){
        
            if(root == null){
        
                return new int[]{
        0, 0};
            }
            
            // 分类讨论的标准是：当前结点偷或者不偷
            // 后续遍历
            // 由于需要后序遍历，所以先计算左右子结点，然后计算当前结点的状态值
            int[] dpl = dfs(root.left);
            int[] dpr = dfs(root.right);
    
            // 处理根
            int[] dp = new int[2];
            dp[0] = Math.max(dpl[0], dpl[1]) + Math.max(dpr[0], dpr[1]);// 偷根
            dp[1] = root.val + dpl[0] + dpr[0];// 不偷根
            return dp;
        }
    }

[image-20221209111603255]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/52bf2cea329744e5aec43cec48be86f4.png
[416.]: https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
[1049._ II]: https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
[494.]: https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
[518. _ II]: https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
[377.]: https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html
[70.]: https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html
[474.]: https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
[322.]: https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html
[279.]: https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html
[Link 1]: https://leetcode.cn/problems/house-robber/
[image-20221209122152699]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/534f44aec198417ead22a9be34b0532d.png
[Link 2]: https://leetcode.cn/problems/house-robber-iii/
[image-20221209142200554]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7d311fa3a0c84dc18aafffc4a01ede07.png