使用f[i]表示前i个能抢到的最大值，如何转移：第i个分抢与不抢两种情况，取最大值即可，抢：f[i] = nums[i] + f[i – 2]，不抢：f[i] = f[i – 1]

不使用滚动数组空间复杂度O(n)

class Solution {
public:
    int rob(vector<int>& nums) {
        int length = nums.size();
        int f[length];
        for(int i = 0; i < length ; i ++){
            f[i] = 0;
        }
        f[0] = nums[0];
        if(length == 1)return f[0];
        f[1] = max(nums[0], nums[1]);
        for(int i = 2;i < length;i++){
            int choose = f[i - 2] + nums[i];
            int not_choose = f[i - 1];
            f[i] = max(choose, not_choose);
        }
        return f[length - 1];
    }
};

由于只需要数组的i – 1,i – 2个元素，所以没必要存储之前的元素，使用滚动数组空间复杂度O(1)

class Solution {
public:
    int rob(vector<int>& nums) {
        int a,b;
        int length = nums.size();
        a = nums[0];
        if(length == 1)return a;
        b = max(nums[0], nums[1]);
        for(int i = 2;i<length;i++){
            int choose = nums[i] + a;
            int not_choose = b;
            a = b;
            b = max(choose, not_choose);
        }
        return b; 
    }
};