题意

You are a professional robber planning to rob houses along a street. Each house has a certain 
amount of money stashed. All houses at this place are arranged in a circle. That means the 
first house is the neighbor of the last one. Meanwhile, adjacent houses have security system 
connected and it will automatically contact the police if two adjacent houses were broken into 
on the same night.

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.

样例

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

1.解题思路

  单从解题方法来看，我们可以找到有效的解决方法，一是回溯法，这道题是非常典型的回溯法中子集树问题，但是从题意来看，这道题使用回溯法不合适，因为会超时；二是动态规划，通常来说，符合子集树的问题，都能用动态规划来实现。所以这道题只能使用动态规划来解答。
  我们很容易得到动态规划的方程：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])。不过，这道题有一点小特殊，就是所有房子构成了一个圆，最重要的限制就是首尾不能相连，也就是说偷第一个房子，就不能偷最后一个房子，反之亦然。而动态规划有一个特点，就是不能存储之前的状态，这就导致这个题稍微的有一个点点复杂。
  我们可以使用一种方式考虑这个问题，有头则无尾，无头则有尾。我们在做动态规划时，要么从第1个遍历到倒数第二个，要么从第二个遍历到倒数第一个，这样就避免了同时偷第一家和最后一家的情况。接下来，我们来看看代码。

2. 代码

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(rob(nums, 0, nums.length - 1), rob(nums, 1, nums.length));
    }

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