题解 | 打家劫舍(二)

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> dp1(n + 1), dp2(n + 1);

        // 不偷最后一家
        for (int i = 0; i < n - 1; i++) {
            dp1[i + 2] = max(dp1[i + 1], dp1[i] + nums[i]);
        }
        // 不偷第一家
        for (int i = 1; i < n; i++) {
            int j = i - 1;
            dp2[j + 2] = max(dp2[j + 1], dp2[j] + nums[i]);
        }
        return max(dp1[n], dp2[n]);
    }
};