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