Leetcode 213. House Robber II

213. House Robber II

Total Accepted: 33705
Total Submissions: 106420
Difficulty: Medium

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.

思路：基本想法和Leetcode 198. House Robber类似，就是形成了环。不过可以这么考虑：在房间数>=2时，盗窃第0间或者不盗窃第0间，取2种情况的较大值。

代码：

 1 class Solution {
 2 public:
 3     int rob(int low,int high,vector<int> nums){
 4         int pre=0,cur=0,i;
 5         for(i=low;i<=high;i++){
 6             cur=max(cur+nums[i],pre);
 7             swap(cur,pre);
 8         }
 9         return pre;
10     }
11     int rob(vector<int>& nums) {
12         int n=nums.size();
13         if(n<2) return n?nums[0]:0;
14         return max(rob(0,n-2,nums),rob(1,n-1,nums));
15     }
16 };