状态机模型

该题是在198题的基础上将将店铺变成了一个环形，我们只需要做两次dp即可。
- 第一次是可以选第一家，那么最后一家一定不选。
- 第二次是一定不选第一家，那么最后一家可以选。

时间复杂度$O(N)$,空间复杂度$O(N)$

空间可以用变量优化到常数级别

参考文献

lc究极班

AC代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int f[n + 1][2], res = INT_MIN;
        memset(f, -0x3f, sizeof f);
        //可以偷第一家
        f[0][0] = 0;
        for (int i = 1 ; i < n ; i ++) {
            int w = nums[i - 1];
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w;
        }
        res = max(f[n - 1][0], f[n - 1][1]);
        //一定不偷第一家
        memset(f, -0x3f, sizeof f);
        f[1][0] = 0;
        for (int i = 2 ; i <= n ; i ++) {
            int w = nums[i - 1];
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w;
        }
        res = max(res,max(f[n][0], f[n][1]));
        return res;        
    }
};