LC198　打家劫舍¶

中等通过率 56.6%python3核心代码模式动态规划样例通过牛客 AC数组动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

每家只有偷与不偷两种选择，偷了就必须跳过上一家，取两者较大者递推。

解题思路¶

这题考什么¶

「相邻不能同时选」的最大权和，是线性动态规划最经典的入门形态，见线性 DP。

关键是把决策落到「最后一家」上。考虑前 i 家时，第 i 家只有两种命运：

不偷它 —— 收益就是前 i-1 家的最优解，第 i-1 家偷不偷都不受影响；
偷它  —— 第 i-1 家必须放弃，只能接在**前 i-2 家**的最优解后面。

两种情况互斥且穷尽，取较大者即可。

状态定义：f[i] 表示只考虑前 i 家房屋时能偷到的最高金额。转移方程：

f[i] = max(f[i-1], f[i-2] + nums[i-1])

右边的 nums[i-1] 是第 i 家的金额（f 的下标从 1 起，数组下标从 0 起，差一格）。初值 f[0] = 0（一家没有，收益 0）、f[1] = nums[0]。

这里必须辨明一个常见的错误直觉：「隔一家偷一家」并不总是最优。 nums = [2, 1, 1, 2] 的最优解是偷第 1 家与第 4 家，中间隔了两家。正因为间隔不固定，才需要 DP 逐位比较，贪心的固定步长会漏掉这类解。

f[i] 只用到 f[i-1] 与 f[i-2] 两项，数组这一维可以整个滚掉，只留两个标量：进入循环体时 prev = f[i-2]、cur = f[i-1]，一次同时赋值就把窗口向右推一格。

数据规模与复杂度¶

1 <= nums.length <= 100，0 <= nums[i] <= 400。时间 O(n)，最多 100 轮循环；空间 O(1)，只有两个标量。答案上界是 100 * 400 = 40000，远在任何整数类型的范围内。与之对照的暴力枚举要试遍所有「不含相邻元素」的子集，数量恰是斐波那契数量级，n = 100 时天文数字，完全不可行。

坑在哪¶

两个标量的初值都取 0，含义是「还没看任何一家」时 f[-1] 与 f[0] 都是 0。由于金额非负（题面保证 0 <= nums[i]），从 0 起手不会让某个正数解被压住。若题目允许负数金额，这个初值就要改成负无穷，否则答案会被 0 顶掉。
prev, cur = cur, ... 必须同时赋值。拆成两句先写 prev = cur，再算 cur 时用到的 prev 已经变成新值，转移就退化成「每家都能偷」。
take 里加的是 prev（f[i-2]）而不是 cur（f[i-1]）。写成 cur + x 等于允许连偷相邻两家，直接违反题意，且样例 [1,2,3,1] 会算出 7。
返回的是 cur 不是 prev。循环结束时 cur 才是「考虑完全部房屋」的最优解， prev 停在倒数第二家。
不需要为 n = 1 单独开分支：只跑一轮时 take = 0 + nums[0]，与 cur = 0 比较后自然得到 nums[0]。

样例复核¶

nums = [2, 7, 9, 3, 1]。

x=2: take = 0+2 = 2 > 0     -> prev=0, cur=2
x=7: take = 0+7 = 7 > 2     -> prev=2, cur=7
x=9: take = 2+9 = 11 > 7    -> prev=7, cur=11
x=3: take = 7+3 = 10 < 11   -> prev=11, cur=11
x=1: take = 11+1 = 12 > 11  -> prev=11, cur=12

返回 12，对应偷第 1、3、5 家（2 + 9 + 1），与期望输出一致。

参考实现¶

solutions/leetcode/LC198/sol.py
from typing import List, Optional


class Solution:
    def rob(self, nums: List[int]) -> int:
        # 滚动掉的是「房屋下标」这一维：整个 f 数组压成两个标量。
        # 进入循环体时 prev = f[i-2]、cur = f[i-1]。
        # 初值都取 0 表示「一家都还没考虑」；题面保证金额非负，从 0 起手不会压住正解
        prev, cur = 0, 0
        for x in nums:
            # 偷这一家：上一家必须放弃，收益只能接在 f[i-2] 后面，绝不能用 cur
            take = prev + x
            # 同时赋值：右边整体先求值，窗口向右滑一格。
            # 不偷这一家时直接沿用 f[i-1]，于是新的 cur 就是两者取大
            prev, cur = cur, take if take > cur else cur
        # 循环结束时 cur 才是「考虑完全部房屋」的最优解，prev 停在倒数第二家
        return cur

LC198 打家劫舍¶