用一个数组f[i]表示抢劫1$\to$i家能获得的最大收益. 按最后一个不同点划分, 不抢第i家, 就是f[i-1]; 抢第i家, 那么第 i-1 家不能抢, 就是 f[i-2]+a[i].

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

        int res = 0;
        vector<int> f(n);
        // 不选最后一家
        for (int i = 0; i < n - 1; i++) {
            if (!i) { f[i] = a[0]; continue;}
            f[i] = f[i - 1];
            if (i >= 2) f[i] = max(f[i], f[i - 2] + a[i]);
        }
        res = max(res, f[n - 2]);

        f[0] = 0;   // 不选第一家
        for (int i = 1; i < n; i++) {
            if (i == 1) f[i] = a[1];
            else f[i] = max(f[i - 1], f[i - 2] + a[i]);
        }
        res = max(res, f[n - 1]);

        return res;
    }
};