题解 | #打家劫舍(二)#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here

        int n = nums.size();

        if(n==1)
            return nums[0];
        else if(n==2)
            return max(nums[0], nums[1]);

        // 按照是否选择nums[n-1] 分为两种情况  最后计算两类情况的最大值
        int ans1, ans2;
        // 选择 nums[n-1] 0 和 n-2 都一定不能选
        int a1 = 0, b1 = nums[1];
        // 否则 初始值正常  两套初始值
        int a2 = nums[0], b2 = max(nums[0], nums[1]);

        for(int i=2; i<n; ++i)
        {
            if(i==n-1) // 只有在最后一刻 才特殊处理
            {
                ans1 = nums[i] + a1;
                ans2 = b2;
            }
            else // 中间的转移公式仍是完整的 和之前一样
            {
                ans1 = max(nums[i] + a1, b1);
                ans2 = max(nums[i] + a2, b2);
            }

            // 更新

            a1 = b1;
            b1 = ans1;

            a2 = b2;
            b2 = ans2;
        }

        return max(ans1, ans2);

    }
};

还是自己的做法 O(n) O(1)

分情况讨论