原題地址

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

題意

之前做過一題House Robber展运，意思是一個(gè)搶劫犯不能搶劫相鄰的兩座房子臭蚁，否則會觸發(fā)報(bào)警器，給出從每個(gè)房子能搶到的價(jià)值，返回?fù)尳俜改軗尩降淖畲笾怠?br> 這里規(guī)則也是一樣涵但，只不過房子變成環(huán)形排列的了涧尿，即，最后一座房子和第一座房子是相鄰的珊燎。

思路

分兩種情況轉(zhuǎn)換成之前的house robber問題：

1. 不搶最后一座房子惭嚣。這樣就相當(dāng)于從環(huán)里去掉了最后一座房子，問題變成了簡單的house robber問題悔政，只不過房子數(shù)目由n 變?yōu)閚-1.
2. 搶最后一座房子晚吞，這樣就相當(dāng)于去掉了第一座房子和最后兩座房子，房子長度為n-3的簡單的house robber問題谋国，最后把這個(gè)n-3的house robber問題結(jié)果加上從最后一座房子能搶到的價(jià)值槽地，就是這種情況下的最大值。
   比較以上兩種情況結(jié)果的大小芦瘾，返回較大的那一個(gè)闷盔。

踩坑

1. 因?yàn)榈诙N情況要稍微調(diào)整一下數(shù)組的下標(biāo)，可能不小心就寫錯(cuò)了旅急。
2. 下面這個(gè)遞推公式容易搞錯(cuò)逢勾，雖然很好理解。藐吮。溺拱。記錄一下吧

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

3. 還是上面的公式逃贝，可能把后面的+nums[i] 寫進(jìn)max的括號里，只給某個(gè)值加上迫摔。

代碼

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);
    }
};