写在前
本类型题目要求不能偷盗相邻房屋，即对于当前房屋我们选择偷或者不偷两种状态，对应我们的最大收益值的更新（动态规划）。
1.打家劫舍（198-中）
题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 ：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
思路：动态规划实现：由于相邻的两家店不能偷。对于第 n 家店，我们只能选择偷或者不偷，然后取两种情况的最大值。
dp[n]数组：前n天能够带来的最大收益- 状态转移方程：
dp[n] = Math.max(dp[n - 2] + nums[n - 1], dp[n - 1] )。
代码：
public int rob1(int[] nums) { int n = nums.length; if (nums == null || n == 0) { return 0; } int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = nums[0]; for (int i = 2; i < n + 1; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]); } return dp[n]; }
我们更新dp[i]的时候，只需要dp[i - 1]以及dp[i - 2]的信息（这里分别用pre2和pre1表示），再之前的信息就不需要了，所以可以进行空间优化。
public int rob2(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int pre1 = 0, pre2 = 0; for (int i : nums) { int tmp = Math.max(pre2, pre1 + i); pre1 = pre2; pre2 = tmp; } return pre2; }
2.打家劫舍II（213-中）
题目描述：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 ：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
思路：这道题区别案例1就是数组是环形，即偷了第一家就不能偷最后一家。
- 偷第一家，也就是求出在前
n - 1家中偷的最大收益，也就是不考虑最后一家的最大收益。 - 不偷第一家，也就是求第
2家到最后一家中偷的最大收益，也就是不考虑第一家的最大收益。
然后只需要返回上边两个最大收益中的衔接的即可。图示的话就是下边的两个范围。
X X X X X X ^ ^ X X X X X X ^ ^
dp数组和状态转移方程均相同，区别在于我们进行状态转移的区间有两个，取最大值。具体见代码。
代码：
public int rob(int[] nums) { //边界条件 int n = nums.length; if (n == 0) return 0; if (n == 1) return nums[0]; return Math.max(robHelper(nums, 0, n - 2), robHelper(nums, 1, n - 1)); } private int robHelper(int[] nums, int start, int end) { int pre1 = 0, pre2 = 0; for (int i = start; i <= end; ++i) { int cur = Math.max(pre2, pre1 + nums[i]); pre1 = pre2; pre2 = cur; } return pre2; }
3.打家劫舍III（337-中）
题目描述：在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 :
输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
思路：标准的动态规划，为了避免过多重复计算，用HashMap存放某一节点能偷到的最大值。
法1：相互连接的父子节点不能同时偷，即转化为偷还是不偷root节点。
- 偷root节点，可以偷root的孙子结点，只要节点不为空，以此类推...
- 不偷root节点，可以偷root的左右子结点，只要左右节点不为空，以此类推...
法2：另外比较好的思路，以每个节点状态为基本状态，返回一个节点偷和不偷的最大值。
- 分别得到出当前节点，左右子节点偷与不偷的利润列表
- 根据规则进行更新，
res[0]代表偷，res[1]代表不偷，本质和法1类似。
代码1：比较常规思路。
public int rob(TreeNode root) { // 存放某一节点偷到的最大值 HashMap<TreeNode, Integer> map = new HashMap<>(); return rob1(root, map); } private int rob1(TreeNode root, HashMap<TreeNode, Integer> map) { if (root == null) return 0; if (map.containsKey(root)) return map.get(root); // 计算偷root节点和孙子节点的情况 int num = root.val; if (root.left != null) { num += rob1(root.left.left, map) + rob1(root.left.right, map); } if (root.right != null) { num += rob1(root.right.left, map) + rob1(root.right.right, map); } // 与只偷左右子节点比较取较大值 int res = Math.max(num, rob1(root.left, map) + rob1(root.right, map)); map.put(root, res); return res; }
代码2：每个节点都有两个状态，偷或者不偷，自底向上的递归求解。
public int rob(TreeNode root) { int[] result = rob2(root); return Math.max(result[0], result[1]); } // 返回值为偷或者不偷的root的最大值 public int[] rob2(TreeNode root) { //{0, 0} if (root == null) return new int[2]; int[] res = new int[2]; // 左右孩子节点偷或者不偷情况 int[] left = rob2(root.left); int[] right = rob2(root.right); // res[0]代表偷，res[1]代表不偷 res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); res[1] = right[0] + left[0] + root.val; return res; }
