198 - House Robber

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
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 @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.
Hide Tags
Dynamic Programming
Hide Similar Problems
(M) House Robber II

因为要做House Robber II，所以把一个多月前做的这一题翻出来，
不看不知道，一看吓一跳，旧代码丑陋得一屁，羞愧得无以复加，赶紧重写一遍吧。
标准DP，没啥可说的，状态方程就是前前一个的值加上自己，比上前一个，取大的那个。
class Solution {
public:
    int rob(vector<int>& nums) {
        int sz = nums.size();
        for(int ii=0; ii<sz; ++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 sz?nums[sz-1]:0;
    }
};
0 ms.

旧代码，虽然也是 0 ms，但真的是难看得自己都受不了啊。。。
class Solution {
public:
    int rob(vector<int>& nums) {
       
        int sz = nums.size();
       
        if(!sz)
            return 0;
        if(1==sz)
            return nums[0];
        if(2==sz)
            return max(nums[0], nums[1]);
        if(3==sz)
            return max(nums[0] + nums[2], nums[1]);
       
        int rst = INT_MIN;
        int base_1 = nums[0];
        int base_2 = max(nums[0],nums[1]);
        for(int ii=2; ii<sz; ii+=2)
        {
            base_1 = max(base_1 + nums[ii], base_2);
           
            if(sz>(ii+1))
                base_2 = max(base_2 + nums[ii+1], base_1);
            int bigger  = max(base_1, base_2);
            if(rst<bigger)
                rst = bigger;
        }
       
        return rst;
    }
};