213. House Robber II

Same idea with House Robber I. We only need to do the dp twice for two different cases.

Case 1: the thief robs the first house and has to skip the last house, i.e. 0 - (n-2).

Case 2: the thief robs the second house and is able to rob the last house too. i.e. 1 - (n-1).

dp[i] indicates the maximum treasure the thief can collect at house i.

1:  class Solution {  
2:  public:  
3:    int rob(vector<int>& nums) {  
4:      int n = nums.size();  
5:      if (n == 0) return 0;  
6:      if (n == 1) return nums[0];  
7:      if (n == 2) return max(nums[0], nums[1]);  
8:      vector<int> sum1(n, 0);  
9:      vector<int> sum2(n, 0);  
10:      sum1[0] = nums[0];  
11:      sum1[1] = sum1[0];  
12:      for (int i = 2; i < n-1; i++) {  
13:        sum1[i] = max(sum1[i-2]+nums[i], sum1[i-1]);  
14:      }  
15:      sum2[1] = nums[1];  
16:      for (int i = 2; i < n; i++) {  
17:        sum2[i] = max(sum2[i-2]+nums[i], sum2[i-1]);  
18:      }  
19:      return max(sum1[n-2], sum2[n-1]);  
20:    }  
21:  };  

Note, we only care of two previous state, i.e. sum[i-2] and sum[i-1], so only two variables are needed. The space can be reduced to O(1).