[LeetCode] House Robber II

House Robber II

Note:This is an extension ofHouse 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 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.

Credits:Special thanks to@Freezenfor adding this problem and creating all test cases.

解题思路：

这个是偷东西的升级版。偷东西1版是一条街上一排房子，每个房子里面有金钱若干，其警报系统很怪，只有触发相邻的两个房间，警报系统才发出警报。问如何偷才能得到最大的值。

这个升级版就是这条街不再是一字排开，而是一个环形街，第一个房子与最后一个房子相邻。问如何偷才能得到最大值？

最初的想法是，记录第一个房间是否被偷了，若被偷了，那么最后一个房间就不能偷。然后分情况讨论。但是如何记录第一个房间被偷了呢？似乎比较麻烦。

其实可以有双向扫描法，第一次从左向右扫描，采用动态规划，若d[len-2]==d[len-1]，说明最后一个房间我们并没有偷，，这种情况跟线性街道是一样的，返回d[len-1]即可，若不相等，说明线性街道时，最后一个房间需要偷，但是我们并不知道第一个房间是否偷了，因此我们还需要扫描一次，从左往右扫描，同样采用动态规划，得出dr[]。

此时有两个动态规划数组d[]和dr[]，注意d[]中d[len-1]!=d[len-2]。我们不知道第一间房是否偷了。假如第一间房间偷了，最后一间房不能偷，那么我们返回d[len-2]。假如第一间房没有偷，我们返回dr[1]，而不管最后一间房是否被偷。因此，我们只需要返回dr[1]和d[len-2]的较大值即可。

代码比较好懂，发现自己越解释越难懂，唉~ps，leetCode计时坏了吗？为何我的代码跑出来只需0ms？

class Solution {public:int rob(vector<int>& nums) {int len = nums.size();if(len == 0){return 0;}if(len == 1){return nums[0];}if(len == 2){return max(nums[0], nums[1]);}int d[len];d[0]=nums[0];d[1]=max(nums[0], nums[1]);for(int i=2; i<len; i++){d[i]=max(d[i-1], nums[i]+d[i-2]);}if(d[len-1]==d[len-2]){ //表明最后一家没有偷，跟线性的一样return d[len-1];}//反向扫描int dr[len];dr[len-1]=nums[len-1];dr[len-2]=max(nums[len-1], nums[len-2]);for(int i=len-3; i>=0; i–){dr[i]=max(dr[i+1], nums[i]+dr[i+2]);}return max(dr[1], d[len-2]);}};

我们一直在旅行，一直在等待某个人可以成为我们旅途的伴侣，