【动态规划】代码随想录算法训练营第四十七天 |198.打家劫舍，213.打家劫舍II ，337.打家劫舍III （待补充）

梦里梦外; 2024-04-23 04:31 77阅读 0赞

## 198.打家劫舍 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 1]

3、题目：

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

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

*  示例 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 。

提示：

*  0 <= nums.length <= 100
 *  0 <= nums\[i\] <= 400

4、视频链接：

[动态规划，偷不偷这个房间呢？| LeetCode：198.打家劫舍\_哔哩哔哩\_bilibili][LeetCode_198._bilibili]

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];
        }
    }

## 213.打家劫舍II ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

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

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

示例 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 = \[0\]
 *  输出：0

提示：

*  1 <= nums.length <= 100
 *  0 <= nums\[i\] <= 1000

4、视频链接：

[动态规划，房间连成环了那还偷不偷呢？| LeetCode：213.打家劫舍II\_哔哩哔哩\_bilibili][LeetCode_213._II_bilibili]

class Solution {
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0)
                return 0;
            int len = nums.length;
            if (len == 1)
                return nums[0];
            return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
        }
    
        int robAction(int[] nums, int start, int end) {
            int x = 0, y = 0, z = 0;
            for (int i = start; i < end; i++) {
                y = z;
                z = Math.max(y, x + nums[i]);
                x = y;
            }
            return z;
        }
    }

## 337.打家劫舍 III ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

![2701cbe41b40e32bda7ce2075cfa57f2.png][]

4、视频链接：

[动态规划，房间连成树了，偷不偷呢？| LeetCode：337.打家劫舍3\_哔哩哔哩\_bilibili][LeetCode_337._3_bilibili]

// 状态标记递归
    // 执行用时：0 ms , 在所有 Java 提交中击败了 100% 的用户
    // 不偷：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
    // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
    // Math.max(rob(root.right)[0], rob(root.right)[1])
    // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
    // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
    class Solution {
        public int rob(TreeNode root) {
            int[] res = robAction1(root);
            return Math.max(res[0], res[1]);
        }
    
        int[] robAction1(TreeNode root) {
            int res[] = new int[2];
            if (root == null)
                return res;
    
            int[] left = robAction1(root.left);
            int[] right = robAction1(root.right);
    
            res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            res[1] = root.val + left[0] + right[0];
            return res;
        }
    }

[. - _LeetCode]: https://leetcode.cn/problems/house-robber/
[Link 1]: https://www.programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_198._bilibili]: https://www.bilibili.com/video/BV1Te411N7SX
[. - _LeetCode 1]: https://leetcode.cn/problems/house-robber-ii/
[Link 2]: https://www.programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_213._II_bilibili]: https://www.bilibili.com/video/BV1oM411B7xq
[. - _LeetCode 2]: https://leetcode.cn/problems/house-robber-iii/
[Link 3]: https://www.programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[2701cbe41b40e32bda7ce2075cfa57f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/1b7baba7a1404a3ca1918674d30ed5ca.png
[LeetCode_337._3_bilibili]: https://www.bilibili.com/video/BV1H24y1Q7sY