小偷问题-打家劫舍

这个问题同学面试的时候问到过，作为一道动态规划问题，就整理一下吧。

题目描述

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

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

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

题解

分析一下问题，唯一的制约条件就是：不能偷取相邻的两间房屋的东西！

假设你已经分析出这是一个动态规划问题，那么状态转移方程是什么？

我们要得到的是： 能偷取的最大金额

那么我们就设置当前遍历到的位置i 获取的最大金额为dp[i]

状态转移方程： dp[i] = Max(dp[i-1],dp[i-2] +nums[i])

解释一下，偷到第i个房间获取的最大金额为 第i-1个房间的金额 或者 i-2个房间的金额+当前房间金额 中的较大值

代码

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];
        }
        // 状态转移方程
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i=2; i<len;i++){
            dp[i] = Math.max(dp[i-2]+ nums[i],dp[i-1]);
        }

        return dp[len-1];
        
    }
}

优化方法：

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];
        }
        //仍然只需要两个状态保持
        int pre = nums[0];
        int cur = Math.max(nums[0],nums[1]);

        for(int i=2;i<len;i++){
            int tmp = cur;
            cur = Math.max(pre+nums[i], tmp);
            pre = tmp;
        }
        return cur;
    }
}

进阶题目：

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

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

• 题目的特殊之处就在于 这是一个首位相连的房屋
• 但是我们不要慌 方法还是一样的
• 只是需要一个额外的分类讨论
• 假设 我们偷第一间房间 就不偷最后一间 此时问题就对应问题一 但范围是（0，n-1）
• 假设 我们不偷第一间房间 那么就可以偷最后一间 此时问题范围是（1，n）
• 利用上一题的方法求解上述两个子问题 两者中较大的就是答案

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];
        }else if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }
             
        return Math.max(robrange(nums,0,len-2),robrange(nums,1,len-1));

    }

    public int robrange(int[] nums,int start,int end){
        //仍然只需要两个状态保持
        int pre = nums[start];
        int cur = Math.max(nums[start],nums[start+1]);

        for(int i=start+2; i<=end; i++){
            int tmp = cur;
            cur = Math.max(pre+nums[i], tmp);
            pre = tmp;
        }
        return cur;
    }
}

337.打家劫舍3

这道题目实际上就是把原来的数组的遍历换成了二叉树的遍历

对于二叉树 ，我们可以使用深度优先搜索来遍历

使用动态规划，我们分析一下子问题;l

对于当前节点i ，我们有两种状态 1》。偷取该节点（子节点不能偷）2》。不偷该节点（左右子节点的和）

那么最终的结果就是两种状态的较大值

代码：

class Solution {
    // 动态规划 小偷能否盗取 与上一时刻的状态有关
    // 遍历二叉树 深度优先dfs
    // 两个数组分别代表 f->偷取该节点金额   g->不偷取该节点金额
    Map<TreeNode,Integer> f = new HashMap<TreeNode,Integer>();
    Map<TreeNode,Integer> g = new HashMap<TreeNode,Integer>();    
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root,0),g.getOrDefault(root,0));
    }

    public void dfs(TreeNode root){
      if(root == null){
          return;
      }  
      dfs(root.left);
      dfs(root.right);
      f.put(root,root.val + g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0));
      g.put(root,Math.max(f.getOrDefault(root.left,0),g.getOrDefault(root.left,0)) + Math.max(f.getOrDefault(root.right,0),g.getOrDefault(root.right,0)));
    }
}