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