打家劫舍2

思路：

把这个环形的街道转化为直线，因为第一个房子和最后一个房子不能同时打劫，因此可以把这个环形街道分为两部分，1到第n-1间房子和2到第n间房子。 
然后，考虑这个直线的房子，可以用动态规划解决，我们可以注意到，第i间房子对应的最大金额由第i-1间房子和第i-2间房子的最大金额决定，即dp(i) = max(dp(i-1),dp(i-2)+nums[i])

代码：

public static int rob(int[] nums) {
	 if(nums == null || nums.length == 0) {
         return 0;
     }

     if(nums.length == 1)
         return nums[0];

     if(nums.length == 2) {
         return Math.max(nums[0], nums[1]);
     }
  // 从第一个开始 就不要最后一个 不要第一个 就可以考虑最后一个
     //// 从第一个开始 就不要最后一个
     int[] dp1 = new int[nums.length];
     dp1[0] = nums[0];
     dp1[1] = Math.max(nums[0], nums[1]);

     for (int i = 2; i < nums.length - 1; i++) {
         dp1[i] = Math.max(nums[i] + dp1[i - 2], dp1[i - 1]);
     }
   //  不要第一个 就可以考虑最后一个
     int[] dp2 = new int[nums.length];
     dp2[0] = 0;
     dp2[1] = nums[1];

     for (int i = 2; i < nums.length; i++) {
         dp2[i] = Math.max(nums[i] + dp2[i - 2], dp2[i - 1]);
     }

     return Math.max(dp1[nums.length - 2], dp2[nums.length - 1]);
 }