Leetcode打家劫舍系列问题

喜欢ヅ旅行 2022-09-12 11:44 153阅读 0赞

**目录**

打家劫舍一

打家劫舍二

打家劫舍三

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

### 打家劫舍一 ###

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的**唯一制约**因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。  
给定一个代表每个房屋**存放金额的非负整数数组**，计算你**不触动警报装置**的情况下 ，一夜之内能够偷窃到的最高金额。

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

其实题目的意思就是像下面这样的一排房子，每个房子里面存有一定数量（非负数）的现金

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_12_color_FFFFFF_t_70_g_se_x_16][]

相邻的两个房屋不能偷

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16][]

问在不触动警报装置（即相邻房屋不能同时偷）的情况下所能取得的最大金额。

一、可以采用递归的思想进行解决

如下图所示，假设小偷走到第一间房间，小偷有 **偷** 和 **不偷** 两种选择。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16][]

（1）**选择偷**，根据题目要求，相邻的房子不能连续偷，这时只能去下下个房子，如下图

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16 1][]

（2）**选择不偷**，此时可以走到下一个房子作选择，如下图所示。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16][]

经过上面分析，发现没，问题的规模变小了，那走到每一个房间时是确定偷还是不偷？其实可以通过求最大值，确定选择哪个。

定义如下**递归函数**

public int rob(int[] nums,int start){}

**递归终止条件**

如果房间走完了就可以停止
    
    即：start >= nums.length

**递归函数等价关系式**

int result = Math.max(
        rob(nums,start + 1 ),    //不选，那可以跳到下一个房间继续选择
        rob(nums,start + 2 ) + nums[start] //选择，则只能到下下个房间去做处理
    )

最终代码如下：

private int rob(int[] nums, int start) {
            //终止条件
            if (start >= nums.length) {
                return 0;
            }
            
            //到 start 时可以选择偷或者不偷，至于最终选择哪一个，采用最大值
            int result = Math.max(rob(nums, start + 1), nums[start] + rob(nums, start + 2));
            return result;
        }

但是这段代码放到LeetCode上运行是会**超时**的，为什么会超时？主要是因为存在很多重复的子问题，可以通过下图看

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16][]

会存在很多重复计算的情况，消除重复计算就是用备忘录。直接上代码

public class Solution {
        private HashMap<Integer, Integer> caches = new HashMap<Integer, Integer>();
    
        private int rob(int[] nums, int start) {
            if (start >= nums.length) {
                return 0;
            }
    
            //先从缓存里面去查找
            if (caches.containsKey(start)) {
                return caches.get(start);
            }
            int result = Math.max(rob(nums, start + 1), nums[start] + rob(nums, start + 2));
            
            //放入缓存
            caches.put(start, result);
            return result;
        }
    }

加了缓存后，可以去除很多不必要的计算

二、动态规划的思想解决

定义 dp\[ i \] 表示第 i 个房间开始到结尾所能偷的最多的钱。

则有 dp\[ i \] = Math.max( dp\[ i + 1\] , dp\[ i + 2 \] + nums\[ i \] )。和递归的等价转化方程式是一样的。只是递归是从前往后（自顶向下）的处理，动态规划是从后往前（自低向上）的处理。

base case

// len表示房间的数量，
    dp[ len - 1 ] = Math.max(dp[len],nums[len-1] + dp[ len + 1 ]).
    
    //所以基准条件就是 
    dp[len] = 0, dp[len + 1 ] = 0

代码如下：

public int rob(int[] nums) {
            int len = nums.length;
            //len + 2 表示需要两个额外的空间
            int[] dp = new int[len + 2];
    
            //base case
            dp[len] = 0;
            dp[len + 1] = 0;
    
            for (int i = len - 1; i >= 0; i--) {
                //状态转移
                dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
            }
            return dp[0];
        }

其实空间还可以进一步优化：根据动态规划的转移方程，我们知道，计算dp\[ i \] 时，只用到  
dp\[ i+1\] 和 dp\[i + 2\] 两个位置，至于dp\[ i + 3\]... dp\[ i + n\]我们是不需要了，所以我们可以用两个变量来表示。代码如下：

public int rob(int[] nums) {
            int dp_i_1 = 0;
            int dp_i_2 = 0;
            for (int i = nums.length - 1; i >= 0; i--) {
                int temp = Math.max(dp_i_1, nums[i] + dp_i_2);
                dp_i_2 = dp_i_1;
                dp_i_1 = temp;
            }
            return dp_i_1;
        }

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

### 打家劫舍二 ###

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 **围成一圈** ，这意味着**第一个房屋**和**最后一个房屋**是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。  
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

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

其实与打家劫舍198，不同的是，上面一个题，房屋是排成一列的，即第一间房子和最后一间房子是不相连的，但是这一题房屋是形成一个**圆圈**，即最后一间房和第一间房是相邻的。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 1][]

当房屋形成环时，第一间房和最后一间房是相邻的，那第一间房和最后一间房有三种状态可供选择.

（1）第一间（用下标0表示）和最后一间（用下标 n - 1 表示）都不偷，则在接下来的 **1 - > n - 2** 范围内的房间里面进行选择，问题转换为和198类似的，只是198题是从 0 -> n - 1 范围内的最大值

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 1][]

result = rob(nums,1 ,n-2);

（2）第一间（下标 0 ）偷、则最后一间（下标 n - 1）只能选择不偷。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16][]

//第一间被偷，则相邻的第二间也不能被偷，只能从第三间开始
    result = nums[0] + rob(nums,2 ,n-2);

（3）第一间（下标 0）不偷，最后一间偷（下标 n - 1）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 2][]

result = rob(nums,1,n-3) + nums[n-1]

第一间和最后一间其实就上面三种情况（因为不能同时偷），那最终的结果就是

result = Math.max(情况1,情况2,情况3);

代码如下：

private static int rob(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            if (nums.length == 1) return nums[0];
    
            int n = nums.length;
            //第一间偷 或者最后一间偷的最大值
            int result = Math.max(nums[0] + rob(nums, 2, n - 2), rob(nums, 1, n - 3) + nums[n - 1]);
    
            //都不偷的最大值
            result = Math.max(result, rob(nums, 1, n - 2));
            return result;
        }
    
        private static int rob(int[] nums, int start, int end) {
            if (end < start) return 0;
            int dp_i_1 = 0;
            int dp_i_2 = 0;
            for (int i = end; i >= start; i--) {
                int temp = Math.max(dp_i_1, nums[i] + dp_i_2);
                dp_i_2 = dp_i_1;
                dp_i_1 = temp;
            }
            return dp_i_1;
        }

**其实可以再稍微简化下**

分为两种情况，因为两间房屋不能同时偷窃，那可以分为如下两种情况

（1）第一间房屋（用0表示）不偷，则表示可偷窃的范围是 1 - > n - 1 范围内的房间

result = rob(nums,1,n-1);

（2）最后一间房屋（用 n - 1表示）不偷，则表示可偷窃的范围是 0 - > n - 2 范围内的房间

result = rob(nums,0,n-2);

代码如下：

public int rob(int[] nums) {
    //空房屋列表
            int n = 0;
            if (nums == null || (n = nums.length) == 0) return 0;
            //一间房，直接返回
            if (nums.length == 1) return nums[0];
            //两间房，返回大的一间
            if (nums.length == 2) return Math.max(nums[0], nums[1]);
    
            return Math.max(rob(nums, 1, n - 1), rob(nums, 0, n - 2));
        }
    
        private  int rob(int[] nums, int start, int end) {
            int dp_i_1 = 0;
            int dp_i_2 = 0;
            for (int i = end; i >= start; i--) {
                int temp = Math.max(dp_i_1, nums[i] + dp_i_2);
                dp_i_2 = dp_i_1;
                dp_i_1 = temp;
            }
            return dp_i_1;
        }

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

### 打家劫舍三 ###

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

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

**示例一**

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

**示例二**

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

其实这个题还是类似的，可以使用备忘录加递归的形式进行解决。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16][]

如上图，当走到一个房间（二叉树中的一个节点）时，可以选择抢或者不抢，至于选择抢或者不抢，就可以使用求最值即可

class Solution {
        private  HashMap<TreeNode, Integer> caches = new HashMap<>();
        public int rob(TreeNode root) {
    if (root == null) return 0;
    
            if (caches.containsKey(root)) {
                return caches.get(root);
            }
            //抢
            int select = root.val + (root.left == null ? 0 : rob(root.left.left)+rob(root.left.right)) + (root.right == null ? 0 : rob(root.right.right)+rob(root.right.left));
            //不抢
            int not_select = rob(root.left) + rob(root.right);
            //求最值
            int result = Math.max(select, not_select);
            caches.put(root, result);
            return result;
        }
    }

[还可以进行进行优化，使用一个大小为 2 的数组来表示][2]

int[] res = new int[2] //res[0] 代表不偷，res[1] 代表偷

**任何一个节点能偷到的最大钱的状态可以定义为**

(1)当前节点不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
    (2)当前节点 偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
    表示为公式如下
    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[] result = robInternal(root);
            return Math.max(result[0], result[1]);
        }
    
    public int[] robInternal(TreeNode root) {
        if (root == null) return new int[2];
        int[] result = new int[2];
    
        int[] left = robInternal(root.left);
        int[] right = robInternal(root.right);
    
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = left[0] + right[0] + root.val;
    
        return result;
        }
    }

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

题目来源

[打家劫舍一][Link 1]

[打家劫舍二][Link 2]

[打家劫舍三][Link 3]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/44c6d05468a8433fac447f888facd43c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0c08b4b0645445829bbbe1b6b6625470.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/87d4848301904c0bb4b2bb3d5ba59b49.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/26355f49ad944122a1cce57d26ca9e54.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a1d22cbb8b194481be23e24c0ec8d692.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a8cd07b3c10742208ec2062009e1e92a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/6ae589c3dca44a6ea720dd1dcd7dd4c7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/73b6f37cc0694e9ba24ff92dbc9db557.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/55ccef619b534198820e83ae85874871.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/3abc3946417346a29d513537e257c9a6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/64a9874d27154772abb8e6e25e09807e.png
[2]: https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/
[Link 1]: https://leetcode-cn.com/problems/house-robber/
[Link 2]: https://leetcode-cn.com/problems/house-robber-ii/
[Link 3]: https://leetcode-cn.com/problems/house-robber-iii/