198. 打家劫舍
class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) return 0;if (nums.length == 1) return nums[0];int[] dp = new int[nums.length];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 -2] + nums[i], dp[i - 1]);}return dp[nums.length - 1];}
}dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房。
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
213. 打家劫舍 II
class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0)return 0;int len = nums.length;if (len == 1)return nums[0];return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));}int robAction(int[] nums, int start, int end) {int[] dp = new int[end]; // 创建 dp 数组，大小为 endfor (int i = start; i < end; i++) {if (i == start) {dp[i] = nums[i]; // 第一个房屋} else if (i == start + 1) {dp[i] = Math.max(nums[start], nums[i]); // 前两个房屋的最大值} else {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); // 状态转移}}return dp[end - 1]; // 返回最后一个房屋的最大抢劫金额}
}此题是 198. 打家劫舍 的拓展版： 唯一的区别是此题中的房间是 环状排列 的（即首尾相接），而 198. 题中的房间是 单排排列 的；而这也是此题的难点。
环状排列 意味着第一个房子和最后一个房子中 只能选择一个偷窃，因此可以把此 环状排列房间 问题约化为两个 单排排列房间 子问题：
在不偷窃第一个房子的情况下（即 nums[1:]），最大金额是 p
在不偷窃最后一个房子的情况下（即 nums[:n−1]），最大金额是 p
综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1,p2) 。
337. 打家劫舍 III
class Solution {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;}
}方案一
4 个孙子偷的钱 + 爷爷的钱 VS 两个儿子偷的钱 哪个组合钱多，就当做当前节点能偷的最大钱数。这就是动态规划里面的最优子结构
public int rob(TreeNode root) {if (root == null) return 0;int money = root.val;if (root.left != null) {money += (rob(root.left.left) + rob(root.left.right));}if (root.right != null) {money += (rob(root.right.left) + rob(root.right.right));}return Math.max(money, rob(root.left) + rob(root.right));
}作者：房建斌学算法
方案二
我们这次使用哈希表来存储结果，TreeNode 当做 key，能偷的钱当做 value
public int rob(TreeNode root) {HashMap<TreeNode, Integer> memo = new HashMap<>();return robInternal(root, memo);
}public int robInternal(TreeNode root, HashMap<TreeNode, Integer> memo) {if (root == null) return 0;if (memo.containsKey(root)) return memo.get(root);int money = root.val;if (root.left != null) {money += (robInternal(root.left.left, memo) + robInternal(root.left.right, memo));}if (root.right != null) {money += (robInternal(root.right.left, memo) + robInternal(root.right.right, memo));}int result = Math.max(money, robInternal(root.left, memo) + robInternal(root.right, memo));memo.put(root, result);return result;
}作者：房建斌学算法
方案三
我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷，1 代表偷
任何一个节点能偷到的最大钱的状态可以定义为
当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
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;
}作者：房建斌学算法