solution

和 1 相比

如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。

https://programmercarl.com/0213.打家劫舍II.html#思路 • 情况一：考虑不包含首尾元素 • 情况二：考虑包含首元素，不包含尾元素 • 情况三：考虑包含尾元素，不包含首元素

（情况 2 3 都包括了 情况 1）

所以只要两遍 打家劫社 1 就可以了

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        int x = robRange(nums, 0, n - 2);
        int y = robRange(nums, 1, n - 1);
        return max(x, y);
    }

    int robRange(vector<int>& nums, int l, int r) {
        int n = r - l + 1;
        if (n == 2) return max(nums[l], nums[l + 1]);
        int a = nums[l], b = max(nums[l], nums[l + 1]), c;
        for (int i = 2; i < n; i++) {
            c = max(a + nums[l + i], b);
            a = b;
            b = c;
        }
        return c;
    }
};

answer

April 14, 2024 1:49 AM (GMT+8)

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int x = helper(nums, 0, n - 2); // robber 1st
        int y = helper(nums, 1, n - 1); // robber last
        return max(x, y);
    }

    int helper(vector<int>& nums, int l, int r) {
        int n = r - l + 1;
        if (n == 1) return nums[l];
        if (n == 2) return max(nums[l], nums[l + 1]);
        int a = nums[l], b = max(a, nums[l + 1]);
        for (int i = 2; i < n; i ++) {
            int c = max(a + nums[l + i], b);
            a = b;
            b = c;
        }
        return b;
    }
};

真的是kua~ chua~地在写