力扣labuladong一刷day11拿下打家劫舍问题共3题
力扣labuladong一刷day11拿下打家劫舍问题共3题
文章目录
- 力扣labuladong一刷day11拿下打家劫舍问题共3题
- 一、198. 打家劫舍
- 二、213. 打家劫舍 II
- 三、337. 打家劫舍 III
一、198. 打家劫舍
题目链接：https://leetcode.cn/problems/house-robber/
思路：打劫必须隔1家，定义dp[i]表示截止到第i家，所能抢到的最大值。
递推公式 dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
如果当前这家不偷，最大值就是dp[i-1]，如果偷就是要隔一家dp[i-2]+nums[i]
class Solution {public int rob(int[] nums) {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-1], dp[i-2]+nums[i]);}return dp[nums.length-1];}
}
由于只用到了前一天和前两天，所以还可以优化一下空间。
public int rob(int[] nums) {if (nums.length == 1) return nums[0];int a = nums[0], b= Math.max(nums[0], nums[1]);for (int i = 2; i < nums.length; i++) {int c = Math.max(b, a+nums[i]);a = b;b = c;}return b;}
二、213. 打家劫舍 II
题目链接：https://leetcode.cn/problems/house-robber-ii/
思路：直接划分为两个区间然后分别计算再比较。即nums[0, len-2] 和 nums[1, len-1]
class Solution {public int rob(int[] nums) {if (nums.length == 1) return nums[0];if (nums.length == 2) return Math.max(nums[0], nums[1]);int max = 0, a = nums[0], b = Math.max(nums[0], nums[1]);for (int i = 2; i < nums.length - 1; i++) {int c = Math.max(b, a+nums[i]);a = b;b = c;}max = b;a = nums[1];b = Math.max(nums[1], nums[2]);for (int i = 3; i < nums.length; i++) {int c = Math.max(b, a+nums[i]);a = b;b = c;}return max > b ? max : b;}
}
三、337. 打家劫舍 III
题目链接：https://leetcode.cn/problems/house-robber-iii/
思路：定义nums[2] 记录每个节点偷与不偷的状态。
class Solution {public int rob(TreeNode root) {int[] ints = f1(root);return Math.max(ints[0], ints[1]);}int[] f1(TreeNode root) {int[] nums = new int[2];if (root == null) {return nums;}int[] left = f1(root.left);int[] right = f1(root.right);nums[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);nums[1] = root.val + left[0] + right[0];return nums;}
}