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

和打家劫舍(一) 思路差不多，优化问题，考虑动态规划。 和一的区别是这里是一个环形，第一个和最后一个也有限制关系。 问题的求解一定包含如下决策：(可以)选择第一个或者一定不选第一个。 如果可以选择第一个，那么我们直接忽视最后一个，当作打家劫舍一来求解，得到一个答案。 如果一定不选第一个, 那么 dp[0] = 0, dp[1] = nums[1], 依然可以按照打家劫舍一来求解。

int rob(vector<int>& nums) {
        int len = nums.size();
        if(len < 2)return nums[0];
        vector<int> dp;
        dp.resize(len);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < len-1; i ++)dp[i] = max(nums[i] + dp[i-2], dp[i-1]);
        
        int ans = dp[len-2];
        dp[0] = 0;
        dp[1] = nums[1];
        for(int i = 2; i < len; i ++)dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
        ans = max(ans, dp[len-1]);
        
        return ans;
    }