BM78　打家劫舍(一)¶

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

牛客原题　源码

讲解章节：线性 DP

一句话

每家只有「偷」与「不偷」两种处置，滚动两个变量往前推。

解题思路¶

这题考什么¶

带「相邻互斥」约束的最优化 DP，按最后一个决策分类，与跳台阶（BM63）同构，只是把方案计数换成了取最大值。

状态定义：dp[i] = 只考虑前 i 家房子时能偷到的最大金额。第 i 家（下标 i-1）只有两种处置，两类合起来覆盖全部方案：

偷它 —— 第 i-1 家必须放过，收益 dp[i-2] + nums[i-1]
不偷 —— 收益就是 dp[i-1]

转移方程：

dp[0] = 0
dp[1] = nums[0]
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])        i >= 2

答案是 dp[n]。「偷了第 i 家就必须跳过第 i-1 家」这条约束之所以能用 dp[i-2] 一笔带过，是因为 dp[i-2] 已经是前 i-2 家的最优解，它内部怎么选与第 i 家无关——无后效性正体现在这里。

dp[i] 只用到前两项，两个变量滚动即可，空间 O(1)： prev 代表 dp[i-2]、cur 代表 dp[i-1]。

数据规模与复杂度¶

1 <= n <= 2e5，1 <= num[i] <= 5000，时限 2 秒（其他语言）。单趟扫描，时间 O(n)、空间 O(1)。金额上界约 1e5 * 5000 = 5e8，不涉及大整数。

坑在哪¶

prev、cur 必须同时更新。元组赋值的右侧全部取旧值，拆成 prev = cur 与 cur = max(...) 两条语句后，第二条会读到刚被改写的 prev，等价于允许偷相邻两家，答案偏大。
循环里不显式区分 dp[1]：初值 prev = cur = 0 让第一轮自动算出 max(0, 0 + nums[0]) = nums[0]，与 dp[1] 的定义一致，所以不必特判。
题面保证 num[i] >= 1，dp 单调不减，不存在「多偷一家反而更少」的情形；若允许负值，则「不偷」这一支仍然必要，转移式本身不用改。
答案是 cur 而不是 prev：循环结束时 cur = dp[n]，prev 停在 dp[n-1]。

样例复核¶

[1,2,3,4]：(prev, cur) 依次 (0,1) -> (1,2) -> (2,4) -> (4,6)，答案 6，对应偷第 2、4 家（2 + 4），与期望输出一致。

参考实现¶

solutions/nowcoder/BM78/sol.py
from typing import List, Optional


class Solution:
    def rob(self, nums: List[int]) -> int:
        # prev = dp[i-2], cur = dp[i-1]，滚动变量省掉整张 dp 表。
        # 两个 0 分别对应 dp[0] = 0 与「还没开始」的虚拟一格，第一轮自然算出 dp[1] = nums[0]
        prev, cur = 0, 0
        for v in nums:
            # 元组赋值右侧全用旧值：不偷这家取 cur，偷这家取 prev + v（跳过相邻的一家）。
            # 拆成两条语句会让第二条读到已更新的 prev，等于允许偷相邻两家
            prev, cur = cur, cur if cur > prev + v else prev + v
        return cur

BM78 打家劫舍(一)¶