Day42——Dp专题

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

---

五、多重背包

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

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

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

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

例如：

背包最大重量为10。

物品为：

重量价值数量物品01152物品13203物品24302

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

和如下情况有区别么？

重量价值数量物品01151物品01151物品13201物品13201物品13201物品24301物品24301

毫无区别，这就转成了一个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)); } } } 六、背包问题总结

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

动规五部曲 确定dp数组（dp table）以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 背包递推公式

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

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

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

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

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

动态规划：474.一和零

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

动态规划：322.零钱兑换动态规划：279.完全平方数 遍历顺序

01背包

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

完全背包

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

力扣题目链接

思路

动规五部曲

确定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数组

红框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

力扣题目链接

思路

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

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

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）

依旧是打家劫舍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数组

最后头结点就是 取下标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; } }