算法训练（leetcode）二刷第三十四天 | *198. 打家劫舍、*213. 打家劫舍 II、*337. 打家劫舍 III

*198. 打家劫舍

leetcode题目地址

按照题目要求，不能连续选择两个相邻房屋，因此每个结点的更新有两种状态：选择当前结点或不选。

dp[i]存储当到第i个房屋时的最大收益。

不选：dp[i] = dp[i-1]
选：dp[i] = dp[i-2] + nums[i] 因为不能连续选，因此最近只能在选i-2位置的基础上选当前结点，而dp[i-2]存储的是访问到第i-2个房屋时的最大收益。

和01背包有些相似。

初始化：

• dp[0]初始化为nums[0]，代表只有一个房屋时，第一个房屋的价值就是最大收益。
• dp[1]初始化为max(nums[0], nums[1])，当有两个房屋时，选其中价值高的。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

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

*213. 打家劫舍 II

leetcode题目地址

本题首位相接增加了难度。

可以将问题拆解为两部分：

• 只考虑首不考虑尾
• 只考虑尾不考虑首
  二者取最大即可。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {
    public int rob(int[] nums) {
        if(nums.length==1) return nums[0];
        int n = nums.length;
        int result1 = Rangerob(nums, 0, n-2);
        int result2 = Rangerob(nums, 1, n-1);
        return Math.max(result1, result2);
    }
    public int Rangerob(int[] nums, int start, int end){
        if(end == start) return nums[start];
        int n = nums.length;
        int[] dp = new int[n];
        dp[start] = nums[start];
        dp[start+1] = Math.max(nums[start], nums[start+1]);
        for(int i=start+2; i<=end; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[end];
    }
}

*337. 打家劫舍 III

leetcode题目地址

树形动态规划，需要结合递归。

每个结点有两个状态：偷或不偷。

因此使用一个二维数组来记录结点的两个状态下的价值。

dp[0]表示偷当前节点可以获得的最大价值。
dp[1]表示不偷当前结点可以获得的最大价值。

题目要求不能连续偷两个直接相连的结点，也就是偷根节点后孩子节点就不能偷了。

借助后序遍历来进行计算，根节点基于孩子节点的结果计算，即首先需要获取左右节点偷与不偷的最大价值。

设左孩子节点的dp数组为left，右孩子结点的dp数组为right。

设cur表示根节点，若偷cur，则dp[0] = cur.val + left[1] + rigth[1]
若不偷cur，则dp[1] = max(left[0], left[1]) + max(right[0], right[1])

也就是说，偷了cur，就不能再偷左右孩子，而左右孩子的dp数组下标1位置记录的就是不偷该节点的最大价值；
若不偷cur，则对于左右孩子，可以偷也可以不偷，取偷与不偷二者的最大价值。

时间复杂度： $O(n)$
空间复杂度： $O(logn)$

// java
/**
 * 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 = robAction(root);
        return Math.max(res[0], res[1]);
    }

    int[] robAction(TreeNode root){
        int[] res = new int[2];
        if(root == null) return res;
        int[] left = robAction(root.left);
        int[] right = robAction(root.right);
        // 偷
        res[0] = root.val + left[1] + right[1];
        // 不偷
        res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        
        return res;
    }
}