1打家劫舍三部曲

 刷题刷题找工作！

s198.打家劫舍

动态规划：开始打家劫舍！

dp数组表示到第i家的最高金额

dp递归公式，要么抢劫这家，加上i-2所抢的钱，要么不抢，保留上一家的。                                                                                                    

class Solution {public int rob(int[] nums) {//一切的问题都是是否装入int len = nums.length;int[] dp = new int[len+1];dp[0] = 0;dp[1] = nums[0];for(int i=2; i <= len; i++){dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);}return dp[len];}
}

这个题呢，就是要注意考虑细节 ，关于为0，为1，以及初始化的时候是怎么样的，不要以为做出推导公式就万事大吉了。

213.打家劫舍II

. - 力扣（LeetCode）

两次dp，只不过注意范围

class Solution {public int rob(int[] nums) {//如何把证第一间房屋和最后一间房屋不同时偷窃呢。//如果偷窃了第一间，则不能偷窃最后一间，所以范围会变//如果偷最后一间，不能偷第一间//做两次dp不就行了？int len = nums.length;if(len == 1){//不能省，后面有now = nums[i]的赋值return nums[0];}int nums1 = ro(nums, 0, len-1);int nums2 = ro(nums, 1, len-1);return Math.max(nums1, nums2);}public int ro(int[] nums, int i, int len){int now = nums[i];int pre1 = 0, pre2 = 0;while(len-- > 0){now = Math.max(pre1, pre2 + nums[i]);pre2 = pre1;pre1 = now;i++;}return now;}
}

---

 337.打家劫舍III

动态规划：继续打家劫舍！

自己的思路

很好理解，看注释。

但是递归的魅力，超时了。

class Solution {public int rob(TreeNode root) {//如果父亲节点被访问过，直接往左右节点的节点走//如果父亲节点未被访问，比较访问子节点，和不访问子节点的，取最大值//访问下一个节点， 1表示当前节点可以访问return Math.max(dfs(root.left, 1) + dfs(root.right, 1), dfs(root.left, 0) + dfs(root.right, 0) + root.val);}public int dfs(TreeNode root, int flag){//父节点是否访问了if(root == null){return 0;}if(root.left == null && root.right == null ){if(flag == 1){return root.val;}return 0;}if(flag == 0){//不可访问当前节点，只能访问子节点return dfs(root.left, 1) + dfs(root.right, 1);}//访问子节点/访问当前节点int num = Math.max(dfs(root.left, 1) + dfs(root.right, 1), dfs(root.left, 0) + dfs(root.right, 0) + root.val);return num;}
}

题解

优化了一下，通过返回数组，一次遍历就找出访问子节点的最大值和不访问子节点的最大值。

class Solution {public int rob(TreeNode root) {//如果父亲节点被访问过，直接往左右节点的节点走//如果父亲节点未被访问，比较访问子节点，和不访问子节点的，取最大值int[] ans = dfs(root);return Math.max(ans[0], ans[1]);}public int[] dfs(TreeNode root){if(root == null){return new int[]{0, 0};//包括根点的最值，不包括跟节点的最值}int[] left = dfs(root.left);int[] right = dfs(root.right);//这样只遍历一次把最大最小值都放进去了int v1 = left[0] + right[0];//放子节点int v2 = left[1] + right[1] + root.val;v2 = Math.max(v2, v1);//为什么要加这个，因为放根节点的最大值是可以放或者不可以放的，而放子节点是一定不能放当前节点的return new int[]{v2, v1};}
}