首页 > 代码库 > 强盗抢房子(II)
强盗抢房子(II)
题目:和之前一道抢房子一样,区别是增加了一个条件,房子是环形分布的,就是说不能同时偷第一个和最后一个,因为他们也是挨着的。。
思路:最优解很巧妙的想法,我们已经算过直线分布的了,那么环形分布和直线分布是不是有什么相似之处呢??其实直线分布如果在后面加一个财宝为0的房子,就是环形分布。环形分布只要去掉第一个或者最后一个,就是直线分布。。所以我们分别求第一个到倒数第二个房子区间获得的最大值和第二个到最后一个房子获得的最大值,取两者最大即可。。。
public int rob(int[] nums) { int n=nums.length; if(n==0) return 0; if(n ==1) return nums[0]; if(n==2) return Math.max(nums[0],nums[1]);
//0到n-2就是第一个到倒数第二个房子
//1到n-1就是第二个到最后一个房子
return Math.max(f(nums,0,n-2),f(nums,1,n-1)); } private static int f(int[] nums,int s,int e){ int n=nums.length; int[] dp=new int[e-s+1]; dp[0]=nums[s]; dp[1]=Math.max(dp[0],nums[s+1]); for(int i=2;i<e-s+1;i++){ dp[i]=Math.max(dp[i-2]+nums[s+i],dp[i-1]); } return dp[e-s]; }
强盗抢房子(II)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。