LeetCode 198. 打家劫舍

◎

本节目标

用取与不取的前缀最优值处理相邻房屋不能同时选择的约束。

这是动态规划基础与线性状态中相邻互斥选择的母题。

题意与约束

每间房有非负金额，相邻两间不能同时偷取，求可获得的最大金额。

第一反应与重复子问题

面对当前房屋，取它就必须接上前两间的最优答案；不取它则保留前一间的最优答案。这两个前缀最优值反复使用。

状态定义与转移推导

令 skip、take 分别表示处理完前缀后不取或取当前房屋的最大金额。读到金额 x 时，新取值为旧 skip+x，新不取值为 max(skip,take)。

正确性依据

任一合法选择对当前房屋只有取与不取两种互斥情况；每种都连接到唯一允许的更短前缀最优解，因此转移完备。

样例执行过程

[2,7,9,3,1] 依次更新后最大值为 12，对应选择 2,9,1。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int skip = 0, take = 0;
        for (int money : nums) {
            int nextTake = skip + money;
            skip = max(skip, take);
            take = nextTake;
        }
        return max(skip, take);
    }
};

Python

Python 3

class Solution:
    def rob(self, nums: list[int]) -> int:
        skip = take = 0
        for money in nums:
            skip, take = max(skip, take), skip + money
        return max(skip, take)

复杂度分析

时间 O(n)，只保存两个滚动状态，空间 O(1)。

边界与易错点

• 单间房直接取其金额。
• 更新时要先用旧 skip 算新 take，不能覆盖后再读取。

模式迁移

房屋首尾也相邻时分成两段线性 DP；树形版本则把相邻约束迁移到父子节点。