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的基础上，这个题目增加的一个限制就是所有的房屋构成了一个环，在这种情况下保证任不偷盗任意两间相邻的房子。
【思路】
看了别人的好多解法，其实说的都不明不白，我把我的想法分享给大家，肯定让你豁然开朗。
首先：如果房屋不构成一个圈，我们的解法有如下几种可能
1. 头部和尾部的房屋都被抢劫
2. 头部房屋被抢劫，尾部房屋没有被抢劫
3. 头部房屋没有被抢劫，尾部的房屋被抢劫
4. 头部和尾部的房屋都没有被抢劫
如果房屋形成一个环，我们的最优解就只能选择后面的三种情况，第二种情况我们要保证最后一个房屋不能被抢劫，第三种情况要保证第一个房屋不能被抢劫，第四种情况已经包含在前两种情况中了。其实就是在环的连接处保证其中一个不被偷的情况下，求出从剩下的房屋中最多能盗取的金钱数目。
因此在House Robber的基础上我们只要保证结果只能为上面第二和第三种情况即可。代码如下：
public class Solution {
public int rob(int[] nums) {
int len = nums.length;
if(len == 0) return 0;
if(len == 1) return nums[0];
int post2 = nums[len-1];
int post1 = Math.max(nums[len-1], nums[len-2]);
int lable1 = 0;
//保证为第一个房屋不被偷
for(int i = len-3; i >= 1; i--) {
int temp = post1;
post1 = Math.max(post1, nums[i] + post2);
post2 = temp;
}
int result1 = post1;
post2 = 0;
post1 = nums[len-2];
//保证最后一个房屋不被偷
for(int i = len-3; i >= 0; i--) {
int temp = post1;
post1 = Math.max(post1, nums[i] + post2);
post2 = temp;
}
int result2 = post1;
return Math.max(result1, result2);
}
}