打家劫舍2

改成环形，需要判断首位是否填充，然后分类讨论，首位填充，则最后一位无法填充只能借前一位的解。

class Solution {
public:
    int dp[1000]={0};
    int i,j;
    int rob(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }else if(nums.size()==1){
            return nums[0];
        }else if(nums.size()==2){
            return max(nums[0],nums[1]);
        }else if(nums.size()==3){
            return max(max(nums[1],nums[0]),nums[2]);
        }

        // dp首位填充,奇数偶数最后一位不能有数据
        dp[0]=nums[0];
        dp[1]=nums[0];
        dp[2]=nums[0]+nums[2];
        for(i=3;i<nums.size()-1;i++){
            dp[i]=max(max(dp[i-2],dp[i-3])+nums[i],dp[i-1]);
        }
        dp[nums.size()-1]=dp[nums.size()-2];

        // dp 首位不填充,最后一位可以有
        dp[0]=0;
        dp[1]=nums[1];
        dp[2]=max(nums[1],nums[2]);
        for(i=3;i<nums.size()-1;i++){
            dp[i]=max(max(dp[i-2],dp[i-3])+nums[i],dp[i-1]);
        }
        return max(dp[nums.size()-1],max(max(dp[i-2],dp[i-3])+nums[i],dp[i-1]));
    }
};