动态规划-打家劫舍 I、II、III

灰太狼 2023-09-25 18:30 70阅读 0赞

1.  ## **打家劫舍** ##

**题目链接：**[198. 打家劫舍 - 力扣（LeetCode）][198. _ - _LeetCode]

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

**示例 1：**

> 输入：\[1,2,3,1\]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

**示例 2：**

> 输入：\[2,7,9,3,1\]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

**提示：**

*  1 <= nums.length <= 100

*  0 <= nums\[i\] <= 400

#### **思路：** ####

分析一下，当前房屋的偷与不偷，取决于前一个房屋和前两个房屋是否被偷了，也就是当前状态和前面状态会有一种依赖关系，这个依赖关系就是动归的递推公式

**下面进行动归五步走：**

1.  状态定义：dp\[i\] 表示：考虑下标 i （包括 i）以内的房屋，最多可以偷窃的金额为 dp\[i\]

1.  状态转移：dp\[i\] = Math.max(dp\[i - 1\], dp\[i - 2\] + nums\[i\])

如果不偷第 i 房间，那么 dp\[i\] = dp\[i-1\]，也就是要考虑 i - 1 房屋

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

将两种情况取最大值

1.  初始化：dp\[0\] = nums\[0\] ，dp\[1\] = max(nums\[0\],nums\[1\])

由状态转移方程可以看出，要初始化 dp\[0\] 和 dp\[1\]

dp\[0\] 也就是当下标 i = 0 时，可以偷窃的金额自然就是第一个房屋 nums\[0\]

d\[1\] 也就是当下标 i = 1 时，可以判断 i = 0 的房屋和 i = 1 的房屋哪个金币多，就偷哪个

1.  遍历顺序：从小到大

1.  返回值：dp\[nums.length - 1\]

#### **代码：** ####

/**
         1. 状态定义：考虑下标 i （包括i）以内的房屋，最多可以偷窃的金额为 dp[i]
         2. 状态转移：dp[i] = Math.max(dp[i-2],dp[i-1]+nums[i])
         3. 初始化：dp[0] = nums[0],dp[1] = max(nums[0],nums[1])
         4. 遍历顺序：从小到大
         5. 返回值：dp[nums.length-1]
          */
         publicintrob(int[] nums) {
             intn=nums.length;
             if(n==1) {
                 returnnums[0];
             }
             int[] dp=newint[n];
             dp[0] =nums[0];
             dp[1] =Math.max(dp[0],nums[1]);
             for(inti=2; i<n; i++) {
                 dp[i] =Math.max(dp[i-1],dp[i-2]+nums[i]);
             }
             returndp[n-1];
         }

## **2. 打家劫舍 II** ##

**题目链接：**[213. 打家劫舍 II - 力扣（LeetCode）][213. _ II - _LeetCode]

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

**示例 1：**

> 输入：nums = \[2,3,2\]输出：3解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

**示例 2：**

> 输入：nums = \[1,2,3,1\]输出：4解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。

**示例 3：**

> 输入：nums = \[1,2,3\]输出：3

**提示：**

*  1 <= nums.length <= 100

*  0 <= nums\[i\] <= 1000

#### **思路：** ####

这道题目和上一题 **打家劫舍** 的唯一区别就是成环了，根据题目要求，相邻的两个房屋是不能同时偷的，现在首尾连成环后，对于数组来说，取首元素后那尾元素是不能取的，取了尾元素那首元素也是不能取的。

所以连成环后，就有这三种情况

*  考虑取首元素，不包含尾元素

*  考虑取尾元素，不报含首元素

*  考虑首尾元素都不取

可以看到这里用的是 **“考虑”**，比如情况一，虽然是想要取首元素，但不是必须要取，这里只是考虑，而确定的是情况一中尾元素不取而已。

再次分析，情况一和情况二是包含情况三的，所以只考虑情况一和二

#### **代码：** ####

publicintrob(int[] nums) {
             intn=nums.length;
             if(n==1) {
                 returnnums[0];
             }
             // 取首元素，不取尾元素(传下标)
             intmax1=robAction(nums,0,n-2);
             // 取尾元素，不取首元素
             intmax2=robAction(nums,1,n-1);
             returnmax1>max2?max1 : max2;
         }
         privateintrobAction(int[] nums, intstart, intend) {
             if(start==end) {
                 returnnums[start];
             }
             int[] dp=newint[nums.length];
             dp[start] =nums[start];
             dp[start+1] =Math.max(dp[start],nums[start+1]);
             for(inti=start+2; i<=end; i++) {
                 dp[i] =Math.max(dp[i-1],dp[i-2]+nums[i]);
             }
             returndp[end];
         }

## **3. 打家劫舍 III** ##

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

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

**示例 1:**

> 输入: root = \[3,2,3,null,3,null,1\]输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

**示例 2:**

> 输入: root = \[3,4,5,1,3,null,1\]输出: 9解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

**提示：**

树的节点数在 \[1, 104\] 范围内 0 <= Node.val <= 104

#### **思路：** ####

这道题最直接的想法就是，遍历树，然后根据规则，判断当前节点抢不抢，如果抢了当前节点，那么两个孩子就不能动，如果没抢当前节点，就可以 **考虑** 抢左右孩子，要遍历树，有前中后（深度优先搜索）还有层序遍历（广度优先搜索）的方法，**本题一定是要后序遍历**，因为通过递归函数的返回值来做下一步。

这道题是可以用动态规划来做的，使用状态转移容器来记录状态的变化，这里可以使用一个长度为 2 的数组，记录当前节点偷与不偷所得到的最大金钱。

这道题目也就是树形 dp 的题，在树上进行状态转移，下面用 递归三部曲 + 动归五部曲来分析

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

现在要求的是一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为 2 的数组

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

所以 dp 数组就是一个长度为 2 的数组。

这里有一个问题就是，长度为 2 的数组怎么标记树中每个结点的状态？

注意这个是在递归的过程中，系统栈会自动保存每一层递归的参数。

1.  终止条件

在遍历的过程中，如果遇到空节点，就直接返回，**这也相当于 dp 数组的初始化**

1.  遍历顺序：

遍历这颗树是使用后序遍历，因为要通过递归函数的返回值来做下一步计算。

*  通过递归左结点，得到左结点偷与不偷的金钱

*  通过递归右结点，得到右结点偷与不偷的金钱

1.  确定单层递归的逻辑

*  如果偷当前结点，那么左右孩子就不能偷 val1 = cur.val + left\[0\] + right\[0\]

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

最后当前节点的状态就是 (val2, val1) （也就是不偷当前节点，偷当前节点）

#### **代码：** ####

publicintrob(TreeNode1root) {
             int[] res=robAction(root);
             returnMath.max(res[0],res[1]);
         }
         // 递归函数的参数和返回值
         privateint[] robAction(TreeNode1root) {
             intres[] =newint[2];
             // 终止条件
             if(root==null) {
                 returnres;
             }
             // 遍历顺序
             int[] left=robAction(root.left);
             int[] right=robAction(root.right);
             res[0] =Math.max(left[0],left[1]) +Math.max(right[0],right[1]);
             res[1] =root.val+left[0] +right[0];
             returnres;
         }

[198. _ - _LeetCode]: https://leetcode.cn/problems/house-robber/
[213. _ II - _LeetCode]: https://leetcode.cn/problems/house-robber-ii/
[337. _ III - _LeetCode]: https://leetcode.cn/problems/house-robber-iii/