题目

思路

一句话：每间房只有「偷」和「不偷」两种选择；求「前 i 间的最优」时，答案只依赖前两步，可以一路滚动。

先想最直白的：枚举所有“互不相邻”的下标组合，求和取最大。每个位置都分出偷/不偷两条路，像一棵二叉树，规模大约是 O(2ⁿ)，n=100 时彻底不可行；即使只枚举合法组合，数量也是斐波那契级别，仍是指数增长。

那能不能贪心：每次都挑金额最大的房，再把相邻的划掉？不行。比如 [2, 3, 2]，贪心先拿中间的 3，两边都不能碰，只得 3；实际上拿两头的 2 + 2 = 4 更优。

关键观察：问题有重叠子问题和无后效性。考虑最后一间 i：

• 偷 i：那么 i-1 一定不能偷，答案 = 「前 i-2 间的最优」 + nums[i]。
• 不偷 i：答案 = 「前 i-1 间的最优」。

于是 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。而 dp[i] 只依赖前两项，用两个变量滚动即可，连 dp 数组都不需要。

解法

维护两个变量 prev2（到 i-2 为止的最优）和 prev1（到 i-1 为止的最优），从左到右扫一遍：

1. 算当前最优：cur = max(prev2 + nums[i], prev1)。
2. 滚动：prev2 = prev1，prev1 = cur。
3. 扫完返回 prev1。

以 [10, 4, 3, 12] 为例：

最后 prev1 = 22，对应方案是偷下标 0 和 3。

下图把上面 3 个步骤串成流程，并逐步演示：

C++

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0;          // 到 i-2 为止的最优
        int prev1 = 0;          // 到 i-1 为止的最优
        for (int x : nums) {
            int cur = max(prev2 + x, prev1);   // 偷当前 / 不偷当前，取更大
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

Python