[数据结构与算法]第198、213、337题 打家劫舍（动态规划）

198. 题目描述：

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

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

198.题目解析：

首先我们先从简单的情况进行考虑，如果只有一家，那么我们就只偷这一家，如果两家的话我们就选择金额最大的那一家进行偷窃，但如果有三家的时候比如 [1 2 3]。要不要偷第一家我们需要考虑后面的，在看到第二家金额为2的时候我们肯定就不偷第一家了，选择偷第二家，走到第三家的时候，我们考虑第一家和第三家的金额总和大于第二家，所以最终我们选择了偷窃第一家和第三家，总金额为4。也就是说，我们在判断是否偷窃这一家的时候，需要根据这家之前的最优解，只需要判断这家之前两家之前的最优解加上这家的金额和这家之前一家之前的最优解来决定是否偷这家。递归代码如下：

//递归
class Solution {
    public int rob(int[] nums) {
        return Money(nums,0);
    }
    int Money(int[] nums, int index){
        if(index>=nums.length)return 0;
        return Math.max(Money(nums,index+1),Money(nums,index+2)+nums[index]);
    }
}

指数暴涨！！超出时间限制啦~！

通过对于递归算法的代码观察，前i家的最优偷窃方案，等于前i-1家的最优偷窃方案和前i-2家的最优偷窃方案，所以我们使用一个数组，采用动态优化来降低时间复杂度。代码如下：

// 动态规划
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len==1)return nums[0];
        int[] dp = new int[len];
        dp[len-1] = nums[len-1];
        dp[len-2] = Math.max(dp[len-1],nums[len-2]);
        for(int i = len-3; i>=0; i--){
            dp[i] = Math.max(dp[i+1], nums[i]+dp[i+2]);
        }
        return dp[0];
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39 MB, 在所有 Java 提交中击败了37.85%的用户

213. 题目描述：

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

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

213.题目解析：

该题和上一题唯一的差别就是，因为房子绕成了一个圆圈，那么第一家和最后一家不能够同时偷，那么我们就这样，一分为二，在不能偷第一家的情况下计算能够偷到的最大金额，在不能偷最后一家的情况下计算能够偷到的最大金额，两种情况的最大值，即为本题所对应的最大值，代码如下：

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len==1)return nums[0];
        if(len==2)return Math.max(nums[0],nums[1]);
        return Math.max(cal_money(nums,0,len-2),cal_money(nums,1,len-1));
    }

    int cal_money(int[] nums, int sta , int end){
        int first = nums[sta];
        int second = Math.max(nums[sta+1],nums[sta]);
        for(int i = sta+2; i<=end ; i++){
            int temp = second;
            second = Math.max(first+nums[i],second);
            first = temp;
        }
        return second;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39 MB, 在所有 Java 提交中击败了49.49%的用户

337. 题目描述：

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

337. 题目解析：

本题在上一题的基础上又再一次提高了难度，将所有人家放到了二叉树里面，子结点和父结点不能够同时被偷，这里我们利用所有叶子结点的子结点都为null值，我们把他们当做是财富为0的家，偷不偷都不影响结果，然后使用一个长度为2的整数数组，分别存储对应家偷的最优财富值和不偷的最优财富值。同之前的原理也差不多，但是要注意，若结点A，选择偷的情况下，应该是A的财富值加上不偷A的左结点的财富值最优解和不偷A右结点的财富值最优解之和。在选择不偷的情况下，应该是选择偷A左结点的最优解和选择不偷A左结点的最优解中的最大值加上选择偷A右结点的最优解和选择不偷A右结点的最优解中的最大值。最后返回根结点对应矩阵中的最大值即可。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        return Math.max(dfs(root)[0],dfs(root)[1]);
    }

    int[] dfs(TreeNode root){
        if(root == null ){
            return new int[]{0,0};
        }
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        int select = root.val + l[1] + r[1];
        int notselect = Math.max(l[0],l[1]) + Math.max(r[0],r[1]);
        return new int[]{select,notselect}; 
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了42.09%的用户

内存消耗：41.1 MB, 在所有 Java 提交中击败了43.86%的用户

学习总结：

动态规划最重要的三个部分：

1.?最优子结构（每个最优解都包含子问题的最优解）

2.?递推公式

3.?重叠子问题