面试热题（打家窃舍）

怼烎@ 2023-10-14 13:57 9阅读 0赞

> 一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，**如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警**。
> 
> 给定一个代表每个房屋存放金额的非负整数数组 `nums` ，请计算 **不触动警报装置的情况下** ，一夜之内能够偷窃到的最高金额。
> 
>     输入：nums = [1,2,3,1]
>     输出：4
>     解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
>          偷窃到的最高金额 = 1 + 3 = 4 。

![f4cca0a3b50a46c48f44a4f0e836ed34.png][]

如上图，每个房间放的金子都不同，有多有少，两个房间之间有警报相连，如果同时偷取相连的两个房子，警报就会发出，你就要去蹲局子，那么如何做一个聪明的小偷，在不触发警报的情况下偷取的金额是最大的，接下来，让我们替小偷想一个方案，如何去偷？

我们可以从后往前考虑，假如我们偷取最后一间房间

![ab49ff0e72264bd0b4162156224b1e26.png][]

我们是不是不可以偷取倒数第二间房间，可供的选择就是在倒数第二间之后随便选一家进行偷取

![dd4d021c68374eadb2c2a6fe580242a3.png][]

为了利益最大化，我们是不是应该偷取的是前n-2间房子的最大金额数+最后一间房子的最大金额数就是我们当前可以偷取的最大金额数呢？NONONO,我们还有一种不偷取最后一间房子的情况，偷取n-2房间的情况

![bb44179578cc44518b8f57737697cda5.png][]

我们通过上述的推导就可以将动态转移方程写出来

dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]);

我们设置的dp数组的语意是dp\[i\]是，偷取第i家的最大金额数

我们可以很简单的推导出基本情况，如果没有房间，小偷就得被饿死，如果只有一家，小偷无可奈何，只能被迫的去偷这家，如果有两家，小偷肯定回去偷金额比较多的那家

dp[0]=nums[0];
         dp[1]=Math.max(nums[0],nums[1]);

解题的入参判断肯定少不了，这种入参判断能为你解决不少的麻烦

if(n==0){
             return 0;
         }
         if(n==1){
             return nums[0];
         }

那么我们的代码 就已经写完了

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

打家劫舍II的基本过程和I差不多，就是从一个直线型房屋排列转换为环形房屋排列，这种就应该考虑是n-1房子和0房子偷不偷的问题，其实可以分为两个数组，分别计算可以偷取的最大金额，最后取最大值就ok了，我们下面讲打家窃舍III

我不得不说，这小偷的数据结构学的其实蛮好的，什么样的房屋排列都能让他想到数据结构这块，利用算法的知识进行解决，不当码农可惜了![04743d7dc4fe4f40b9261bf96824f075.gif][]

来让我们言归正传

![3e41c0babc0d44489063661fe07c5385.png][]

对于我们的选择是每个节点是否偷取决定着我们最后的结果

![5d5a7826020247e3aa0feb429d25f765.png][]

如果偷的话，情况又是如何？不偷的时候情况又是怎样的？

![c8597d14b4504dcda87391b9d058b6c9.png][]

![f862664682924627ae2a76dcc0fe6ae7.png][]

看到这幅图大家会想到什么？树的层序遍历，但是树的层序遍历在这里可是不适用的，因为这道题中的有些情况是通过不了，所以我们换种思维想一想，这种题是不是可以用递归的方式解决

假设我们的当前节点是root,递归函数是rob

偷：当前的节点的金额数+rob(节点左树的子左树)+rob(节点左树的右树)+rob(节点右树的左树)+rob(节点右树的右树)

不偷：rob(节点的左树)+rob(节点的右树)

int rob=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 rob_not=rob(root.left)+rob(root.right);

这种递归大概率会超时，所以我们加一个记忆化数组，不用再进行重复计算（进行剪枝）

Map<TreeNode,Integer> map=new HashMap<>();
    
     
      if(map.containsKey(root)){
                return map.get(root);
            }

该题的大致流程就已经讲完了，希望大家可以看的开心，不懂的可以在评论区问我，我看到的话会给大家一一解答

Map<TreeNode,Integer> map=new HashMap<>();
        public int rob(TreeNode root) {
            if(root==null){
                return 0;
            }
            if(map.containsKey(root)){
                return map.get(root);
            }
            int rob=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 rob_not=rob(root.left)+rob(root.right);
            int max=Math.max(rob,rob_not);
            map.put(root,max);
            return max;
        }

[f4cca0a3b50a46c48f44a4f0e836ed34.png]: https://img-blog.csdnimg.cn/f4cca0a3b50a46c48f44a4f0e836ed34.png
[ab49ff0e72264bd0b4162156224b1e26.png]: https://img-blog.csdnimg.cn/ab49ff0e72264bd0b4162156224b1e26.png
[dd4d021c68374eadb2c2a6fe580242a3.png]: https://img-blog.csdnimg.cn/dd4d021c68374eadb2c2a6fe580242a3.png
[bb44179578cc44518b8f57737697cda5.png]: https://img-blog.csdnimg.cn/bb44179578cc44518b8f57737697cda5.png
[04743d7dc4fe4f40b9261bf96824f075.gif]: https://img-blog.csdnimg.cn/04743d7dc4fe4f40b9261bf96824f075.gif
[3e41c0babc0d44489063661fe07c5385.png]: https://img-blog.csdnimg.cn/3e41c0babc0d44489063661fe07c5385.png
[5d5a7826020247e3aa0feb429d25f765.png]: https://img-blog.csdnimg.cn/5d5a7826020247e3aa0feb429d25f765.png
[c8597d14b4504dcda87391b9d058b6c9.png]: https://img-blog.csdnimg.cn/c8597d14b4504dcda87391b9d058b6c9.png
[f862664682924627ae2a76dcc0fe6ae7.png]: https://img-blog.csdnimg.cn/f862664682924627ae2a76dcc0fe6ae7.png