打家劫舍系列（力扣198、213、337）Java动态规划_打家劫舍 iii 回扣

目录

一、打家劫舍（力扣198）

二、打家劫舍II（力扣213）

三、打家劫舍III（力扣337）

---

一、打家劫舍（力扣198）

        198. 打家劫舍-力扣

        此题的动态规划有两种思路：

        1、思路一：

        参考309. 最佳买卖股票时机含冷冻期-力扣 ，我也写的有题解：

        买卖股票系列（力扣121、122、123、188、309、714） Java动态规划

        房屋只有两种状态：被偷 和 没被偷

        那么我们用dp数组来记录第i间房屋时的最大金额，dp[i][0] 记录被偷的情况，dp[i][1]记录没被偷的情况。

        dp[i][0]表示被偷，那么前一间必然没有被偷，当前值就是前一间没有被偷的情况下的金额+当前金额，则dp[i][0] = dp[i-1][1] + nums[i]

        dp[i][1]表示没被偷，那么前一间可能被偷，也可能没被偷，当前值就是这两种情况中较大的那个，则dp[i][1] = max{ dp[i-1][0] , dp[i][1] }

        最后取dp[len-1][0]和dp[len-1][1]的较大值即可。考虑到当前房屋值只与前一间房屋有关，则可以用变量来代替dp数组，就成了下面的代码。

        在买卖股票的题解（上面的链接）中有此方法更详细的讲解和推导过程，感兴趣的朋友可以去看一下。

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

        2、思路二

        对于第k间房屋，只有两种情况：被偷 和 不被偷

        如果被偷，当前金额为k-2间房屋的金额+当前金额

        如果不被偷，当前金额为k-1间房屋金额

        这间房屋的金额就是两个值中较大的那个，所以得到递推公式：

                                                dp[i]=max(dp[i−2]+nums[i],dp[i−1])

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

二、打家劫舍II（力扣213）

        213. 打家劫舍 II-力扣

         这题与上题的不同在于，最后一家与第一家连在了一起，而我们动态规划出来的结果是无法知道第一家是否被偷的。那么，我们是不是可以分而治之，分为第一家被偷和第一家没被偷两种情况去看，这样问题就迎刃而解了。

        其中，偷东西的那部分代码可以抽取成方法，这样代码会更加简洁，但是分开写比较容易看清思路。 

class Solution {
    public int rob(int[] nums) {
        int res;
        int len = nums.length;
 
        if(len == 1) {
            return nums[0];
        }
        if(len == 2) {
            return Math.max(nums[0], nums[1]);
        }
 
        //第一间偷了
        int a;
        int b;
        if(len==3) {
            res = nums[0];
        } else {
            a = nums[2];
            b = 0;
            for(int i=3; i<len-1; i++) {
                int tempA = a;
                int tempB = b;
                a = tempB + nums[i];
                b = Math.max(tempA, tempB);
            }
            res = Math.max(a, b) + nums[0];
        }
 
        //第一间没偷
        a = nums[1];
        b = 0;
        for(int i=2; i<len; i++) {
            int tempA = a;
            int tempB = b;
            a = tempB + nums[i];
            b = Math.max(tempA, tempB);
        }
        res = Math.max(res, Math.max(a, b));
        return res;
    }
}

三、打家劫舍III（力扣337）

        337. 打家劫舍 III-力扣

        这次要偷的房子组成了一棵二叉树，我们简化一下题目：二叉树的节点上有权值，要求不能同时取父子节点的权值，问最大权值和是多少？

        首先，每个节点有两个状态：被偷 和 没被偷。我们使用a(i)来表示第i个节点被偷时，他和他的子树所贡献的最大权值；使用b(i)表示第i个节点不被偷时，他和他的子树所贡献的最大权值。那么：

        因为a(i)表示被偷，所以他的子节点不能被偷，那么他的权值和是左右子树不被偷时的权值和+当前节点权值，即：

                                                a(i) = b(i.left) + b(i.right) + i.val；

        因为b(i)表示当前节点不被偷，那么他的左右节点可以被偷也可以不被偷，我们取权值和较大的情况，即：

                            b(i) = max{a(i.left) , b(i.left)} + max{a(i.right) , b(i.right)}

        最终我们找出a(root) 和 b(root)中的较大值即可。a和b可考虑用哈希表来保存。

/**
 * 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 {
 
    Map<TreeNode, Integer> a;   //a.get(root) 表示当前节点被偷时，他和他的子树所能贡献的最大价值
    Map<TreeNode, Integer> b;   //b.get(root) 表示当前节点没被偷时，他和他的子树所能贡献的最大价值
 
    public int rob(TreeNode root) {
        a = new HashMap<>();
        b = new HashMap<>();
        dfs(root);
        return Math.max(a.get(root), b.get(root));
    }
 
    void dfs(TreeNode node) {
        if(node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        a.put(node, b.getOrDefault(node.left, 0)+b.getOrDefault(node.right, 0)+node.val);
        b.put(node, 
        Math.max(a.getOrDefault(node.left, 0), b.getOrDefault(node.left, 0)) 
        + Math.max(a.getOrDefault(node.right, 0), b.getOrDefault(node.right, 0)));
    }
}

        不难看出，当前的ab值只与他的左右子树的ab值有关，所以，可以考虑将每次调用时的ab值返回给上一级调用，这样可以省去哈希表。

/**
 * 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) {
        int []res = dfs(root);
        return Math.max(res[0], res[1]);
    }
 
    int[] dfs(TreeNode node) {
        if(node == null) {
            return new int[]{0, 0};
        }
        int []left = dfs(node.left);
        int []right = dfs(node.right);
        //表示当前节点被偷时，他和他的子树所能贡献的最大价值
        int a = left[1] + right[1] + node.val;  
        //表示当前节点没被偷时，他和他的子树所能贡献的最大价值
        int b = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{a, b};
    }
}