力扣labuladong一刷day11拿下打家劫舍问题共3题

力扣labuladong一刷day11拿下打家劫舍问题共3题

一、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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

由于只用到了前一天和前两天，所以还可以优化一下空间。

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;
    }
1
2
3
4
5
6
7
8
9
10
11

二、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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19