?

House Robber II

Note: This is an extension of House 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 are arranged 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 tonight without alerting the police.

Credits:
Special thanks to @Freezen for 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
  
   & 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
   
    =0; i--){ dr[i]=max(dr[i+1], nums[i]+dr[i+2]); } return max(dr[1], d[len-2]); } };
   
  

?