题目链接：House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

这道题的是House Robber的扩展，在House Robber基础上更改为房子构成环，也就是说不能同时抢劫第一家和最后一家，因为这两家相邻的。

同样是动态规划的思路，只不过这里遍历两次：

  1. 第一次不抢nums[n-1]；
  2. 第二次不抢nums[0]。

每次都是和House Robber同样的思路，最后返回两者最大值。

时间复杂度：O(???)

空间复杂度：O(???)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution
{
public:
    int rob(vector<int>& nums)
    {
        if(nums.size() == 0)
            return 0;
        if(nums.size() == 1)
            return nums[0];
        
        int pre1 = 0, cur1 = 0;
        for(int i = 0; i < nums.size() - 1; ++ i)
        {
            int temp = pre1;
            pre1 = cur1;
            cur1 = max(temp + nums[i], pre1);
        }
        
        int pre2 = 0, cur2 = 0;
        for(int i = 1; i < nums.size(); ++ i)
        {
            int temp = pre2;
            pre2 = cur2;
            cur2 = max(temp + nums[i], pre2);
        }
        
        return max(cur1, cur2);
    }
};