一、打家劫舍（力扣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）
这题与上题的不同在于，最后一家与第一家连在了一起，而我们动态规划出来的结果是无法知道第一家是否被偷的。那么，我们是不是可以分而治之，分为第一家被偷和第一家没被偷两种情况去看，这样问题就迎刃而解了。
其中，偷东西的那部分代码可以抽取成方法，这样代码会更加简洁，但是分开写比较容易看清思路。
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）
这次要偷的房子组成了一棵二叉树，我们简化一下题目：二叉树的节点上有权值，要求不能同时取父子节点的权值，问最大权值和是多少？
首先，每个节点有两个状态：被偷 和 没被偷。我们使用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}; } }
