首页 > 代码库 > leetcode-House Robber II-213
leetcode-House Robber II-213
输入一个数组，a[i]表示第i位置的房子的价值，这些房子围成一个圈，相邻的两个房子不能同时抢，问能抢到的最大的价值
和这些题是一个系列http://blog.csdn.net/ac_0_summer/article/details/52348192
这里围成一个圈，那么对最后一个房子来说：
1.如果选择这个房子则第一个和倒数第二个都不能选
2.如果没选择这个房子，则第一个和倒数第二个可选可不选
但是当遍历到最后一个房子时，如果确定一个房子在之前的计算中已经选择或没选择呢
做法是遍历两遍：
第一遍计算[0,n-2]，也就是选择第一个房子到倒数第二个房子，因为选择第一个房子，那么肯定不能选最后一个房子
第二遍计算[1,n-1]，也就是从第二个房子到最后一个房子，即：不选第一个房子，因为不选第一个房子的情况下最后一个房子可选可不选
1 class Solution { 2 public: 3 int rob(vector<int>& nums) { 4 int len=nums.size(); 5 if(len==0) return 0; 6 if(len==1) return nums[0]; 7 int dp1[len+1],dp2[len+1]; 8 memset(dp1,0,sizeof(dp1)); 9 memset(dp2,0,sizeof(dp2));10 dp1[0]=nums[0];11 for(int i=1;i<len-1;i++){12 dp1[i]=dp2[i-1]+nums[i];13 dp2[i]=max(dp1[i-1],dp2[i-1]);14 }15 int mx=max(dp1[len-2],dp2[len-2]);16 memset(dp1,0,sizeof(dp1));17 memset(dp2,0,sizeof(dp2));18 dp1[1]=nums[1];19 for(int i=2;i<len;i++){20 dp1[i]=dp2[i-1]+nums[i];21 dp2[i]=max(dp2[i-1],dp1[i-1]);22 }23 int mx2=max(dp1[len-1],dp2[len-1]);24 return max(mx,mx2);25 }26 };
leetcode-House Robber II-213
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。