题解 | 打家劫舍(二)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int max(int a, int b){
        return a>b?a:b;
    }
    int rob(vector<int>& nums) {
        int n = nums.size();
         

        //res1 不偷第一家的情况
        vector<int> dp1(n+1,0);dp1[1] = 0;
        for(int i = 2  ; i <= n ;i++ ){  
            dp1[i] =  max(dp1[i-1],dp1[i-2]+nums[i-1] );
        }
        int res1 = dp1[n];


        //res2 偷第一家的情况
        vector<int> dp2(n,0);
        dp2[1] = nums[0];
        for(int i = 2  ; i < n ;i++ ){  
            dp2[i] =  max(dp2[i-1],dp2[i-2]+nums[i-1] );
        }
        int res2 = dp2[n-1];

        return max(res1,res2);

    }
};

一位dp中等题，对于这种环形问题，可以拆分成2 个方向，一个是要第一个，另一个是不要第一个，拆分成2个来分别动态规划