DP-LeetCode-213. 打家劫舍 II

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

        int ans = INT_MIN;
        vector<int> g(n + 1); // 不偷
        vector<int> f(n + 1); // 偷
        
        // 1.第一家不偷
        for (int i = 2; i <= n; i++) {
            g[i] = max(f[i - 1], g[i - 1]);
            f[i] = g[i - 1] + nums[i - 1];
        }
        
        // 最后一家偷或不偷
        ans = max(f[n], g[n]);
        // 2.第一家偷
        f[1] = nums[0];
        g[1] = 0;
        for (int i = 2; i <= n; i++) {
            g[i] = max(f[i - 1], g[i - 1]);
            f[i] = g[i - 1] + nums[i - 1];
        }

        // 最后一家必偷
        ans = max(ans, g[n]);
        return ans;
    }
};