[LeetCode] House Robber II

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]);
    }
};