213 - 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.
Hide Tags
Dynamic Programming
Hide Similar Problems
(E) House Robber
 
做的是个O(n²)的解，就是从每个起点都算一遍最大利益，算的时候剔除掉从当前位置算起的最后一个。
虽然是0 ms，但是觉得应该又线性解法，一直试图从起点找一个线性的解但是没成功，郁闷。
看到讨论区有个帖子的思路，只要比较去头跟去尾的情况即可，重新写了一个线性的，确实如此。

再看了一遍，这个思路也就是比较从第一个开始，和从第二个开始的结果，
这点之前曾经想到过，但是觉得可能有遗漏，就没细想了，感觉缺少丛数学上的证明，擦……

换句话说，是不是从任何两个相邻的点各算一次，比较结果都可以呢？
画了几个数字验证了一下确实是可行的。
仔细想想，因为构成最大结果的两个/多个数字，必然不相邻，
所以只要验证了相邻的两个数字为起点的两个情形，
肯定其中之一必然是包含最大结果的。（这算是数学证明么…）

class Solution {
public:
    int rob(vector<int>& nums) {
        int sz = nums.size();
       
        //---------------------- solution below is O(n) ----------------------
        if(sz)
        {
            vector<int> noFirst = nums;  //可以不必复制vector，用两个变量翻滚就可以了。
            for(int ii=1; ii<sz; ++ii)
            {
                int lastlast = ii>2 ? noFirst[ii-2] : 0;
                int last____ = ii>1 ? noFirst[ii-1] : 0;
                noFirst[ii] = max(lastlast + noFirst[ii], last____);
            }
   
            for(int ii=0; ii<sz-1; ++ii)
            {
                int lastlast = ii>1 ? nums[ii-2] : 0;
                int last____ = ii>0 ? nums[ii-1] : 0;
                nums[ii] = max(lastlast + nums[ii], last____);
            }
           
            return max(noFirst[sz-1], nums[sz-2]);
        }
        return 0;

        //------------- solution below is O(n^2), not the best. -------------
        if(sz==1)
            return nums[0];
        int rst=0;
        for(int ii=0; ii<sz; ++ii)
        {
            int vvv[sz]={0};
            vvv[1] = nums[ii];
           
            //DP calculation except the element last to ii
            for(int jj=2; jj<sz; ++jj)
            {
                int idx= ii+jj-1 - (ii+jj > sz)*sz;
                vvv[jj] = max(vvv[jj-2] + nums[idx], vvv[jj-1]);
            }
           
            if(rst < vvv[sz-1])
                rst = vvv[sz-1];
        }
        return rst;
    }
};
0 ms，0 ms.