打家劫舍问题1、2、3（动态规划、递归）

旧城等待， 2023-03-06 05:05 27阅读 0赞

## 一、打家劫舍1 ##

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

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

> **示例 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.1 冗余dp ####

**状态定义：**

**dp \[ i \] \[ 0 \] 表示不偷第 i 号房屋能偷到的最多的钱；  
dp \[ i \] \[ 0 \] 表示偷第 i 号房屋能偷到的最多的钱。**

**状态转移方程：**

**dp\[ i \]\[ 0 \] = max( dp\[ i-1 \]\[ 1 \], dp\[ i-1 \]\[ 0 \] )；**

> 因为这家不偷，上家可以不偷、或者偷。

**dp\[ i \]\[ 1 \] = max( dp\[ i-1 \]\[ 0 \] + nums\[ i \] )。**

> 这家要偷，肯定是上一家不偷。

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

#### 1.2 压缩版本1 ####

前面对于 dp 的定义太细化，分了拿和不拿第 i 家的情况下能够获取的最大值，事实上这是一个重复的计算，如果dp本来就是最大值，何必再分拿还是不拿呢？

**状态定义：**

**dp\[ i \] 表示到了第 i 号房的时候能够获得的最大金额。**

**转移方程：**

**dp\[ i \] = max( dp\[ i-2 \] + nums\[ i \] , dp\[ i-1 \] )**

这时候不用考虑上一家的屋子要不要偷，因为 dp\[ i-1 \] 就是更新的最大值，包含了偷或不偷的情况。

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

#### 1.3 压缩版本2 ####

考虑到这个状态转移方程最多只依赖于前两天，所以三个变量就足够了，我们还可以把空间优化到 O(1)

class Solution {
        
        public int rob(int[] nums) {
        
            if( nums.length<1 )return 0;
            if( nums.length<2 )return nums[0];
            int a = nums[0];
            int b = Math.max( nums[0],nums[1] );
            for( int i=2; i<nums.length; i++ ){
        
                int c = Math.max( a + nums[i], b );
                a = b;
                b = c;
            }
            return b;
        }
    }

### 二、打家劫舍 2 ###

在上一道题的基础之上，这个地方所有的房屋都围成一圈，这意味着**第一个房屋和最后一个房屋是紧挨着的。**

说白了，就是从 0 到 n-2 家进行dp；或者从 1 到 n-1 家进行 dp ，取两者最大值。

所以借助打家劫舍 1 的代码，我们还是比较容易写出这道题目的。

class Solution {
        
        public int rob(int[] nums) {
        
            int size = nums.length;
            if( size==0 )return 0;
            if( size==1 )return nums[0];
            if( size==2 )return Math.max(nums[0],nums[1]);
            int dp1 = helper(nums, 0, size-2);
            int dp2 = helper(nums, 1, size-1);
            return Math.max( dp1, dp2 );
        }
        //普通动态规划
        public int helper(int[] nums, int left, int right){
        
            int a = nums[left];
            int b = Math.max(a, nums[left+1]);
            for( int i=left+2; i<=right; i++ ){
        
                int c = Math.max(a + nums[i], b);
                a = b;
                b = c;
            }
            return b;
        }
    }

## 三、打家劫舍 3 ##

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

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

> **示例 1:**  
> 输入: \[3,2,3,null,3,null,1\]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]  
> 输出: 7  
> 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.  
>   
> **示例 2:**  
> 输入: \[3,4,5,1,3,null,1\]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1]  
> 输出: 9  
> 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

**分析：**  
树的问题一般都要用递归来解决，这个题的动态规划的初始可以这样思考：

1.  选择root，那么答案就是root.val + rob（左子树的左右）+rob（右子树的左右）；
2.  不选择root，那么答案就是rob（左子树）+rob（右子树）

#### 3.1 递归 ####

按照上面说的思路，递归就能直接解决这个问题：

class Solution {
        
        public int rob(TreeNode root) {
        
            if( root==null )return 0;
            int a = root.val;
            //左右子树
            int left = rob(root.left);
            int right = rob(root.right);
            
            int ll = root.left == null ? 0 : rob(root.left.left);
            int lr = root.left == null ? 0 : rob(root.left.right);
            int rl = root.right == null ? 0 : rob(root.right.left);
            int rr = root.right == null ? 0 : rob(root.right.right);
    
            return Math.max( left + right , root.val + ll + lr + rl + rr );
        }
    }

但是代码效率非常非常低。

#### 3.2 动态规划 ####

从最上面的分析我们能看出来，递归求解子树的过程，本来就有很多**重复**，子树从上到下，只是根节点的一个个选择与否的问题，而直接递归忽略了记忆这个事，没有用到动态规划。

想要动态规划，就得自底向上，利用缓存将他们存起来，因为树的节点的特殊性，数组不太方便，所以可以借助hashmap

**一个 map 来 存储对于每一个 key（Treenode），选择他的情况下的value（最大值）；  
另一个map来存储对于每一个 key（Treenode），不选择他的情况下的value（最大值）。**

class Solution {
        
        private HashMap<TreeNode, Integer> map1 = new HashMap();//选
        private HashMap<TreeNode, Integer> map2 = new HashMap();//不选
    
        public int rob(TreeNode root) {
        
            if(root==null)return 0;
            dfs(root);
            return Math.max( map1.getOrDefault(root,0), map2.getOrDefault(root,0));
        }
    
        public void dfs(TreeNode node){
        
            if( node == null )return;
            dfs(node.left);
            dfs(node.right);
            //选当前节点，那么不选左右
            map1.put(node, node.val + map2.getOrDefault(node.left, 0) + map2.getOrDefault(node.right, 0));
            //不选当前节点，左右可选可不选，选大的
            map2.put(node, Math.max(map1.getOrDefault(node.left, 0),map2.getOrDefault(node.left, 0))
             + Math.max(map1.getOrDefault(node.right, 0), map2.getOrDefault(node.right, 0)));
        }
    }

#### 3.3 动态规划空间优化 ####

上面的过程我们能看出来，其实做的是**后序遍历**，先求左右再求根，如此向上。

**那么传递到上一层的时候，不需要所有的前置值，用到的总共只有 4 个值，所以其实用临时变量传递就可以，没必要用整个hashmap，也没必要映射。**

这和把线性动态规划的数组优化为几个值是一样的做法。

class Solution {
        
        public int rob(TreeNode root) {
        
            if(root==null)return 0;
            int[] ans = dfs(root);
            return Math.max( ans[0],ans[1] );
        }
    
        //返回当前子树选和不选能够获取的最大值，只用一个包含两个元素的数组
        public int[] dfs(TreeNode node){
        
            if( node == null )return new int[]{
        0,0};
            int[] l = dfs(node.left);
            int[] r = dfs(node.right);
            int[] temp = new int[2];
            //选当前节点，那么不选左右
            temp[0] = node.val + l[1] + r[1];
            //不选当前节点，那么左右求最大（可选可不选）
            temp[1] = Math.max(l[0],l[1])+Math.max(r[0],r[1]);
            return temp;
        }
    }

打家劫舍问题，over。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: /images/20230208/c2a5a00cb2704607849e01cbbfcc28b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1]: /images/20230208/b00922a19f3c4a72b7d67cb2e56c1e34.png