1、思路

• 用原数组来做动态规划，nums[i]表示小偷到达第i家时总共最多能偷到的财物；

• 小偷到达编号为i的房屋时有两种选择，进去偷，或者不进去偷；

• 若进去偷，则nums[i] = nums[i] + nums[i - 2]，即偷这一家和上上家，不偷上家；

• 若不进去偷，则nums[i] = nums[i - 1]，即不偷这家，偷上家。

2、代码

class Solution {
public:
    int rob(vector<int>& nums) {
        //数组长度不足2，直接返回前两个中较大的值即可
        if (nums.size() <= 2) return nums.size() == 1 ? nums[0] : max(nums[0], nums[1]);

        nums[1] = max(nums[1], nums[0]);

        for (int i = 2; i < nums.size(); ++ i)
        {
            nums[i] = max(nums[i - 1], nums[i] + nums[i - 2]);  //两种状态取最大值
        }

        return nums.back();
    }
};