# Leetcode 213. House Robber II
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/house-robber-ii/submissions/ 。

想法 :
* 跟上一題(198)很像，只是變成圓形的環，也就是頭尾不能一起選。
* 改成頭到尾-1做一次，再加上尾到頭+1做一次DP，兩個取大為答案。

時間複雜度 :

程式碼 :

class Solution {
public:
    int rob(vector<int>& nums) {
        int house[410]={0},house2[410]={0},l=nums.size();
        house[0]=nums[0]; 
        if(l == 1) return nums[0];
        if(l >= 2) house[1]=max(nums[0],nums[1]);
        
        for(int i=2 ; i<l-1 ; i++){
            house[i]=max(house[i-1],house[i-2]+nums[i]);
        }
        
        house2[l-1]=nums[l-1];
        if(l >= 2) house2[l-2]=max(nums[l-1],nums[l-2]);
        for(int i=l-1 ; i>=2 ; i--){
            house2[i-2]=max(house2[i-1],house2[i]+nums[i-2]);    
        }
        
        return max(house[l-2],house2[1]);
    }
};