题解 | 打家劫舍(二)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        int n = nums.size();
        const int INF = 1e8;
        if (n == 1) return nums[0];

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

        f[0][0] = 0;
        f[0][1] = -INF;
        for (int i = 1; i < n; i++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        return max(ans, max(f[n - 1][0], f[n - 1][1]));
    }
};