House Robber II（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.

解题思路1：DP

现在房子排成了一个圆圈，则如果抢了第一家，就不能抢最后一家，因为首尾相连了，所以第一家和最后一家只能抢其中的一家，或者都不抢，那我们这里变通一下，如果我们把第一家和最后一家分别去掉，各算一遍能抢的最大值，然后比较两个值取其中较大的一个即为所求。

int rob(int[] nums) {
    int len = nums.length;

    if (len <= 1) return len==0 ? 0 : nums[0];
    return Math.max( rob(nums, 0, len - 1), rob(nums, 1, len ));
}

int rob(int[] nums, int left, int right) {
    int[] dp = new int[right];

    dp[left] = nums[left];
    dp[left + 1] = Math.max(nums[left], nums[left + 1]);
    for (int i = left + 2; i < right; ++i) {
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }
    return dp[right-1];
}

解题思路2：把所有的房子分为奇数家和偶数家，每次交替偷一家。 空间复杂度可以是O(1)

int rob(int[] nums) {
    int len = nums.length;

    if (len <= 1) return len==0 ? 0 : nums[0];
    return Math.max( rob(nums, 0, len - 1), rob(nums, 1, len ));
}

public int rob(int[] nums,int left,int right) {
    int odd = 0;
    int even = 0;
    for (int i = left; i < right; i++) {
        if (i % 2 == 0) {
            even = Math.max(nums[i] + even, odd);
        } else {
            odd = Math.max(nums[i] + odd, even);
        }
    }
    return Math.max(odd,even);
}