[LeetCode]House Robber II

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 arearranged 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 tonightwithout alerting the police.

[思路]这次是对环处理。我们可以把这个问题变换成在直线上处理的子问题。见子问题解法。

因为是环，所以最后一个和第一个不能同时取。

那么这个问题，我们对第一个到倒数第二个求在直线上的解，，再对第二个到最后一个求在直线上的解，取最大值即可。

class Solution {public:int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];return max(RobLine(nums,0,nums.size()-1),RobLine(nums,1,nums.size()));}int RobLine(vector<int> &num,int start,int end ) {if(num.size()==0)return 0;int step1=0;int step2=0;int step3=num[start];int step4=0;for(int i=start+1;i<end;++i){step4=max(num[i]+step2,num[i-1]+step1);step1=step2;step2=step3;step3=step4;}return step3;} };

你有没有这样的感觉，坐在一列火车上，