题解 | #打家劫舍(二)#

动态规划

相同的代码跑两遍，和（一）思路一样

f[i] 表示偷第 i 个房间，g[i] 表示不偷第 i 个房间

这里分两种情况：

1. 不选起点，答案就是 res = max(f[n], g[n]) 最大值

2. 选起点，那么就不能选终点，所以答案就是 res = max(res, g[n])

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        
        // 1. 不选起点
        f[0] = 0, f[1] = 0;
        g[0] = 0, g[1] = 0;
        for (int i = 2; i <= n; i ++ ) {
            f[i] = g[i - 1] + nums[i - 1];
            // 如果不选 i，那么 i - 1 可选可不选
            g[i] = max(f[i - 1], g[i - 1]);
        }
        
        int res = max(f[n], g[n]);
        
        // 2. 选起点，那么就不能选终点
        f[0] = 0, f[1] = nums[0];
        g[0] = 0, g[1] = 0;
        for (int i = 2; i <= n; i ++ ) {
            f[i] = g[i - 1] + nums[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        
        return max(res, g[n]);
    }
};