今天就是打家劫舍的一天，这个系列不算难，大家可以一口气拿下。
198.打家劫舍
视频讲解：https://www.bilibili.com/video/BV1Te411N7SX
https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html
class Solution {
public int rob(int[] nums) {
int[] dp = new int[nums.length];
if(nums.length == 1) return nums[0];
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], nums[i] + dp[i-2]);
}
return dp[nums.length-1];
}
}
213.打家劫舍II
视频讲解：https://www.bilibili.com/video/BV1oM411B7xq
https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html
class Solution {
public int rob(int[] nums) {
if(nums.length == 1) return nums[0];
int res1 = rob(nums, 1, nums.length);
int res2 = rob(nums, 0, nums.length - 1);
return Math.max(res1, res2);
}
public int rob(int[] num, int start, int end){
int[] nums = Arrays.copyOfRange(num, start, end);
int[] dp = new int[nums.length];
if(nums.length == 1) return nums[0];
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], nums[i] + dp[i-2]);
}
return dp[nums.length-1];
}
}
337.打家劫舍III
视频讲解：https://www.bilibili.com/video/BV1H24y1Q7sY
https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html
错误：
class Solution {
public int rob(TreeNode root) {
int[] dp = robtree(root);
return Math.max(dp[0], dp[1]);
}
public int[] robtree(TreeNode root){
if(root == null) return new int[]{0, 0};
int[] left = robtree(root.left);
int[] right = robtree(root.right);
int value1 = root.val + left[1] + right[1];
int value2 = left[0] + right[0];
return new int[]{value1, value2};
}
}
class Solution {
public int rob(TreeNode root) {
int[] dp = robtree(root);
return Math.max(dp[0], dp[1]);
}
public int[] robtree(TreeNode root){
if(root == null) return new int[]{0, 0};
int[] left = robtree(root.left);
int[] right = robtree(root.right);
int value1 = root.val + left[1] + right[1];
int value2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{value1, value2};
}
}
