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};}
}