问题描述
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.
Credits:Special thanks to @Freezen for adding this problem and creating all test cases.
问题分析：这个问题是House Robber I的变种或者升级，将房子的布局由原来的一排变换成现在的环形。环形就意味着多了一个约束：最后一个房子和第一个房子不能同时选择。可以分情况进行讨论，1、不选择第一个房子，2、不选择最后一个房子。所以可以调用两次House RobberI的算法求解。注意特殊对待n=1的情况。 代码如下：
public int rob(int[] nums) { if(nums==null) return 0; int n=nums.length; if(n==0) return 0; if(n==1) return nums[0]; return Math.max(myrob(nums,0,n-1),myrob(nums,1,n-1)); } public int myrob(int[] nums,int st,int len){ int n=len; int[]dprob=new int[n]; int[]dpnrob=new int[n]; dprob[0]=nums[st]; dpnrob[0]=0; for(int i=1;i<n;i++){ dprob[i]=dpnrob[i-1]+nums[st+i]; dpnrob[i]=Math.max(dprob[i-1],dpnrob[i-1]); } return Math.max(dprob[n-1],dpnrob[n-1]); }