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.
在之前一道题上的改进，就是说首位也是相连的，然后求出最大抢劫金钱。
方法就是在之前方法的基础上，如果最后
per + nums[i] > curr && nums[0] + nums[2] > nums[1]
判断一下。其次，就是分两个数组进行判断。
public class Solution { public int rob(int[] nums) { if (nums.length == 0){ return 0; } if (nums.length == 1){ return nums[0]; } int[] nums2 = new int[nums.length]; for (int i = 0; i < nums.length - 1; i++){ nums2[i] = nums[i + 1]; } nums2[nums.length - 1] = nums[0]; return Math.max(robber(nums), robber(nums2)); } public int robber(int[] nums){ int per = nums[0]; int curr = nums[1]; for (int i = 2; i < nums.length; i++){ int num = Math.max(curr, per + nums[i]); if (i == nums.length - 1){ if (per + nums[i] > curr && nums[0] + nums[2] > nums[1]){ return Math.max(Math.max(nums[0], nums[i]) + per - nums[0], curr); } } per = curr; curr = num; } return curr; } }
可以稍微优化一下。
public class Solution { public int rob(int[] nums) { if (nums.length == 0){ return 0; } if (nums.length == 1){ return nums[0]; } return Math.max(robber(nums, 0, nums.length - 1), robber(nums, 1, nums.length)); } public int robber(int[] nums,int start, int end){ int per = 0, curr = 0; for (int i = start; i < end; i++){ int num = Math.max(curr, per + nums[i]); per = curr; curr = num; } return curr; } }
leetcode 213. House Robber II 抢劫房子II---------- java
原文：http://www.cnblogs.com/xiaoba1203/p/6637408.html