BM79　打家劫舍(二)¶

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

牛客原题　源码

讲解章节：线性 DP

一句话

首尾相邻，拆成「不偷最后一家」与「不偷第一家」两条直链各跑一遍。

解题思路¶

这题考什么¶

环形约束的通用拆解手法：枚举一个足以打破环的决策，把环拆成若干条直链。

本题比 BM78 只多一条约束：第 1 家与第 n 家相邻，不能同时偷。这条约束等价于「第一家与最后一家至少有一家没被偷」，于是按这一点分两种情况：

情况 A：放弃最后一家，在 nums[0 .. n-2] 上做线性打家劫舍
情况 B：放弃第一家，  在 nums[1 .. n-1] 上做线性打家劫舍
答案 = max(A, B)

不重不漏从两个方向确认：

不漏：任何合法方案要么没偷最后一家（落进 A），要么没偷第一家（落进 B）；
不错：A、B 两条链里第一家与最后一家不可能同时出现，所以两条链产出的方案全都是合法的。

两条链有重叠（首尾都不偷的方案在 A、B 里各算一次）不影响取最大值。

线性部分的状态与转移完全同 BM78：

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

同样用 prev、cur 两个变量滚动。

数据规模与复杂度¶

1 <= n <= 2e5，1 <= nums[i] <= 5000，时限 4 秒（其他语言）。跑两遍线性 DP，时间 O(n)、空间 O(1)。

坑在哪¶

n == 1 必须单独返回 nums[0]。此时两条链 nums[0:0] 与 nums[1:1] 都是空的，照常跑会返回 0——而唯一的一家并不与自己相邻，本来就该偷。
n == 2 不必特判：A = nums[0]、B = nums[1]，取大者正好是「只能偷一家」的正解。
不能用「先按直链求解，再对同时偷了首尾的方案打补丁」的做法。去掉首尾之一后的最优解未必只差这一处，补丁式修正无法保证仍是最优。
两条链共用一个 line 函数，靠 [lo, hi) 的半开区间划出范围；写成闭区间会让两条链各差一家，answer 偏小或非法。
与 BM78 同源的陷阱：prev、cur 必须同时更新，拆成两条语句就允许偷到相邻两家。

样例复核¶

[1,2,3,4]：A 在 [1,2,3] 上得 4（偷 1 和 3），B 在 [2,3,4] 上得 6（偷 2 和 4），取 6，与期望输出一致。

参考实现¶

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


class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]          # 两条链都会退化成空，唯一的一家不与自己相邻，必须单独返回

        def line(lo: int, hi: int) -> int:
            """在 nums[lo:hi] 这条直链上做线性打家劫舍（半开区间，与 BM78 同构）。"""
            prev, cur = 0, 0        # prev = dp[i-2], cur = dp[i-1]
            for i in range(lo, hi):
                v = nums[i]
                # 右侧全取旧值：不偷取 cur，偷则取 prev + v，自动跳过相邻的一家
                prev, cur = cur, cur if cur > prev + v else prev + v
            return cur

        # 环拆成两条直链：至少有一家首尾不被偷，两种情况覆盖全部合法方案
        a = line(0, n - 1)          # 放弃最后一家
        b = line(1, n)              # 放弃第一家
        return a if a > b else b

BM79 打家劫舍(二)¶