leetcode 213. House Robber II

原题地址

https://leetcode.com/problems/house-robber-ii/description/

题意

之前做过一题House Robber，意思是一个抢劫犯不能抢劫相邻的两座房子，否则会触发报警器，给出从每个房子能抢到的价值，返回抢劫犯能抢到的最大值。
这里规则也是一样，只不过房子变成环形排列的了，即，最后一座房子和第一座房子是相邻的。

思路

分两种情况转换成之前的house robber问题：

1. 不抢最后一座房子。这样就相当于从环里去掉了最后一座房子，问题变成了简单的house robber问题，只不过房子数目由n 变为n-1.
2. 抢最后一座房子，这样就相当于去掉了第一座房子和最后两座房子，房子长度为n-3的简单的house robber问题，最后把这个n-3的house robber问题结果加上从最后一座房子能抢到的价值，就是这种情况下的最大值。
   比较以上两种情况结果的大小，返回较大的那一个。

踩坑

1. 因为第二种情况要稍微调整一下数组的下标，可能不小心就写错了。
2. 下面这个递推公式容易搞错，虽然很好理解。。。记录一下吧

dp[ i] [1] = max( dp[i-2][1], dp[i-1][0]) + nums[i]

3. 还是上面的公式，可能把后面的+nums[i] 写进max的括号里，只给某个值加上。

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        if(n==2) return max(nums[0],nums[1]);
        if(n==3) return max(max(nums[0],nums[1]),nums[2]);
        if(n==4) return max(max(nums[0]+nums[2],nums[1]),nums[1]+nums[3]);
        int dp1[n-1][2],dp2[n-3][2]; //dp[i][0]means don't take the i th value
        for(int i =0;i<n-1;i++) {
            dp1[i][0]=dp1[i][1]=0;
        }
        for(int i =0;i<n-3;i++) {
            dp2[i][0]=dp2[i][1]=0;
        }
        dp1[0][0] = 0;
        dp1[0][1] = nums[0];
        dp1[1][0] = nums[0];
        dp1[1][1] = max(nums[0],nums[1]);
        for(int i =2;i<n-1;i++){
            dp1[i][0]=max(dp1[i-1][0],dp1[i-1][1]);
            dp1[i][1]=max(dp1[i-2][1],dp1[i-1][0])+nums[i];
        }
        int result1=max(dp1[n-2][0],dp1[n-2][1]);

        dp2[0][0] = 0;
        dp2[0][1] = nums[1];
        dp2[1][0] = nums[1];
        dp2[1][1] = max(nums[1],nums[2]);
        for(int i =2;i<n-3;i++){
            dp2[i][0]=max(dp2[i-1][0],dp2[i-1][1]);
            dp2[i][1]=max(dp2[i-2][1],dp2[i-1][0])+nums[i+1];
        }
        int result2= nums[n-1]+max(dp2[n-4][0],dp2[n-4][1]);

        return max(result1,result2);
    }
};