打家劫舍II
其实就是把环拆成两个队列，一个是从0到n-1，另一个是从1到n，然后返回两个结果最大的。
动态规划
而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。
对情况二和情况三分别做打家劫舍，取最大
class Solution { public: int robRange(vector<int>& nums, int start, int end) { if((end - start) == 1 ) return nums[start]; if((end - start) == 2) return max(nums[start],nums[start+1]); vector<int> dp((end - start) , 0); dp[0] = nums[start]; dp[1] = max(nums[start],nums[start+1]); for(int i=2 ; i<(end - start) ;i++) { dp[i] = max(dp[i-1],dp[i-2]+nums[start+i]); } // for(auto it:dp) cout<<it<<' '; // cout<<endl; return dp[end-start-1]; } int rob(vector<int>& nums) { if(nums.size()==0) return 0; if(nums.size()==1) return nums[0]; int result1 = robRange(nums,0,nums.size()-1); int result2 = robRange(nums,1,nums.size()); // cout<<result1<<' '<<result2; return max(result1,result2); } };
二刷
class Solution { public: int robRange(vector<int>& nums , int left, int right) { vector<int> dp (right-left,0); dp[0] = nums[left]; dp[1] = max(nums[left] , nums[left+1]); for(int i=2 ; i<right-left ;i++) { dp[i] = max(dp[i-1] , dp[i-2]+nums[i+left]); } return dp[right-left-1]; } int rob(vector<int>& nums) { if(nums.size()==1) return nums[0]; if(nums.size()==2) return max(nums[0],nums[1]); return max(robRange(nums,0,nums.size()-1) , robRange(nums,1,nums.size())); } };
