思路分析

该题是打家劫舍系列第二题，没有做过第一题的建议先看看第一题，这里贴上 LeetCode 198. 打家劫舍 的题解。

该题相较于第一题其实就只多了一个条件，就是首尾不能同时选择，因此这里会分为三种情况：
1. 选头不选尾
2. 选尾不选头
3. 头尾都不选

根据下图可以清晰地看出，根据闫氏DP分析法则中的不重不漏原则，由于情况1和2已经把情况3包含其中，所以我们只需要对情况1和情况2进行分析即可。

我们的算法思路是分别从前往后和从后往前进行两次DP，区间分别为1 ~ n - 1 和 n ~ 2，接下来的思路就与LeetCode 198. 打家劫舍 一模一样啦

C++ 代码

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

        vector<int> f(n + 1, 0), g(n + 1, 0);
        f[1] = nums[0];
        for (int i = 2; i <= n - 1; i ++)
            f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]);

        g[n - 1] = nums[n - 1];
        for (int i = n - 2; i ; i --)
            g[i] = max(g[i + 1], g[i + 2] + nums[i]);

        return max(f[n -1], g[1]);
    }
};