一、LeetCode198题

1、题目描述

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

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
  偷窃到的最高金额 = 1 + 3 = 4 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、算法思想

　　考虑所有可能的抢劫方案过于困难。一个自然而然的想法是首先从最简单的情况开始。记：f(k) = 从前 k 个房屋中能抢劫到的最大数额，Ai= 第 i 个房屋的钱数。

　　首先看 n = 1 的情况，显然 f(1) = A1? ；再看 n = 2，f(2) = max(A1? , A2? )；

　　对于 n = 3，有两个选项:

• 抢第三个房子，将数额与第一个房子相加。
• 不抢第三个房子，保持现有最大数额。
• 显然，你想选择数额更大的选项。于是，可以总结出公式：f(k) = max(f(k – 2) +Ak? , f(k – 1))

我们选择 f(1) = f(0) = 0 为初始情况，这将极大地简化代码。答案为 f(n)。可以用一个数组来存储并计算结果。不过由于每一步你只需要前两个最大值，两个变量就足够用了。

Java

作者：LeetCode
链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3、代码

public int rob(int[] num) {
　　int prevMax = 0;
　　int currMax = 0;
　　for (int x : num) {
　　　　int temp = currMax;
　　　　currMax = Math.max(prevMax + x, currMax);
　　　　prevMax = temp;
　　}
　　return currMax;
}

二、LeetCode213题

1、题目描述

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

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

示例 1:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、算法思想

　　此题是198. 打家劫舍的拓展版： 唯一的区别是此题中的房间是环状排列的（即首尾相接），而 198. 题中的房间是单排排列的；而这也是此题的难点。环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题：

• 在不偷窃第一个房子的情况下（即 nums[1:]），最大金额是 cur1；
• 在不偷窃最后一个房子的情况下（即 nums[:n-1]），最大金额是 cur2? ；
• 综合偷窃最大金额： 为以上两种情况的较大值，即 max(cur1,cur2) 。
• 下面的任务则是解决 单排排列房间（即 198. 打家劫舍） 问题。
  

3、代码

public int rob(int[] nums) {
        // 利用198题，cur1表示不选第一个的结果，cur2表示不选最后一个的结果
        if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        int pre1=0,pre2=0,cur1=0,cur2=0;

        for(int i=1;i<nums.length;++i){
            int temp=cur1;
            cur1=Math.max((pre1+nums[i]),cur1);
            pre1=temp;
        }
        
        for(int j=0;j<nums.length-1;++j){
            int temp=cur2;
            cur2=Math.max((pre2+nums[j]),cur2);
            pre2=temp;
        }
        return Math.max(cur1,cur2);
    }

三、LeetCode337题

1、题目描述

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

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

示例 1:

输入: [3,2,3,null,3,null,1]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、算法思想

每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷

• 当前节点选择偷时，那么两个孩子节点就不能选择偷了
• 当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)

我们使用一个大小为2的数组来表示 int[] res = new int[2] 0代表不偷，1代表偷
任何一个节点能偷到的最大钱的状态可以定义为：

• 当前节点选择不偷: 当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
• 当前节点选择偷: 当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数

3、代码

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;
}

LeetCode动态规划系列（1）——打家劫舍，LeetCode198、213、337题讲解

原文：https://www.cnblogs.com/SupremeBoy/p/12329053.html