213. 打家劫舍 II

思路：考虑三种情况注释代码中

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size()==1) return nums[0];
        //考虑首端，不考虑尾端
        int value1 = robrange(nums,0,nums.size()-2);
        //考虑尾端，不考虑首端
        int value2 = robrange(nums,1,nums.size()-1);
        return max(value1,value2);
    }

    //考虑以下三种情况
    //1:不考虑首尾的情况
    //2:考虑首端情况
    //3:考虑尾端情况
    //由于情况1包含在情况2，3中，所以只要考虑后面两个即可
    int robrange(vector<int>& nums,int start,int end){
        if (end == start) return nums[start];
        vector<int> dp(nums.size(),0);  //第i个房间最高金额是dp[i]
        dp[start] = nums[start];
        dp[start+1] = max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++){
            dp[i] = max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[end];
    }
};