LeetCode 面试题 17.16. 按摩师

约 6 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
数组 动态规划
目录

题目描述

✅ 面试题 17.16. 按摩师

题意分析

一排房屋各有一笔金额，要求选出一个金额总和最大的子集，唯一的限制是不能偷相邻的两间。

这个限制把每间房屋都变成一道二选一：偷它，就必须放弃它左边那间；不偷它，左边那间怎么选就完全不受影响。也就是说，每个位置的决策只和它紧邻的历史有关，和更远的房屋没有直接冲突。

约束信号也值得留意：房屋数最多 100、金额非负。金额非负意味着「多考察一间房屋，答案不会变差」，我们要的是「前若干间的最优」而不用担心跳过谁会吃亏。

边界上，只有一间房时直接偷它；空数组按 0 处理。

解法：滚动变量动态规划

核心思路

暴力做法是枚举所有「互不相邻」的子集，每间房屋偷或不偷两种选择，共 $2^n$ 种组合，指数级不可接受。

瓶颈在于大量重复计算：不管前面怎么偷的，走到第 i 间时真正有用的信息只有一件事——「前面那些房屋能偷到的最大金额是多少」，具体偷了哪几间根本不重要。

于是钉死状态定义：dp[i] 表示「只考虑前 i 间房屋能偷到的最大收益」（不要求第 i 间一定被偷）。对第 i 间只有两种选择：

  • 不偷它：收益就是前 i - 1 间的最优，即 dp[i - 1]；
  • 偷它：第 i - 1 间必须放弃，收益是 dp[i - 2] + nums[i]。

两者取大，得到转移方程 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。

转移只用到前两项，整条 DP 数组可以压成两个滚动变量：pre 对应 dp[i - 2]（前前一间为止的最优），cur 对应 dp[i - 1]（前一间为止的最优），每处理一间房屋向前滚动一格。

解题步骤

  • 初始化 pre = 0、cur = 0。对应「考虑 0 间房屋收益为 0」，这样第一间房屋能自然套用转移，不必单独特判前两间。
  • 从左到右遍历每个金额 num。因为状态只依赖更早的两个状态，一趟顺序扫描就够。
  • 计算 next = max(cur, pre + num)。cur 是不偷当前这间的收益，pre + num 是偷当前这间的收益，取大即当前最优。
  • 滚动 pre = cur、cur = next。必须先用旧值算完 next 再覆盖，否则「前一间」的信息会被冲掉。
  • 遍历结束返回 cur，即考虑完全部房屋的最大收益。

以 [2,7,9,3,1] 走一遍：初始 pre = 0、cur = 0。第 1 间 2：next = max(0, 0 + 2) = 2，滚动后 pre = 0、cur = 2；第 2 间 7：next = max(2, 0 + 7) = 7，pre = 2、cur = 7；第 3 间 9：next = max(7, 2 + 9) = 11，pre = 7、cur = 11；第 4 间 3：next = max(11, 7 + 3) = 11，pre = 11、cur = 11；第 5 间 1：next = max(11, 11 + 1) = 12，cur = 12。返回 12（偷第 1、3、5 间），与预期一致。

代码实现

class Solution {
    public int massage(int[] nums) {
        int pre = 0;
        int cur = 0;

        for (int num : nums) {
            // 当前房屋偷或不偷，取收益更大的选择。
            int next = Math.max(cur, pre + num);
            pre = cur;
            cur = next;
        }

        return cur;
    }
}

func massage(nums []int) int {
    pre := 0
    cur := 0

    for _, num := range nums {
        // cur 表示不偷当前房屋，pre+num 表示偷当前房屋。
        next := maxInt(cur, pre+num)
        pre = cur
        cur = next
    }

    return cur
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(n)$，每间房屋只做一次常数次比较和加法。
  • 空间复杂度：$O(1)$，转移只依赖前两项，两个滚动变量即可承载全部历史信息。

关键点总结

  • 状态定义要钉死为「前 i 间的最大收益」而不是「偷第 i 间的最大收益」：前者答案就是最后一个状态，后者还得在所有位置里取 max，转移也更绕。
  • 「选或不选 + 只与前两项有关」是一类通用模板：转移只看常数个历史状态时，DP 数组都能压成滚动变量。
  • 双变量初始化为 0, 0 等价于在数组前面垫了两间金额为 0 的虚拟房屋，能消掉 n = 1、n = 2 的特判，白板上更不容易写错。
  • 面试高频追问是环形版 213. 打家劫舍 II：首尾相邻时拆成「不偷第一间」和「不偷最后一间」两次线性 DP 取大，务必能当场推出来。
  • 进一步的变体是把「一排」换成「一棵树」（337）或把「位置相邻」换成「数值相邻」（740），识别出同构后都能落回这条转移方程。

易错点总结

  • 先更新 pre 再算 next：[2,7,9] 上写成 pre = cur; cur = max(cur, pre + num); → 偷与不偷用的是同一个状态，pre + num 变成 cur + num，等于允许偷相邻两间，结果偏大。
  • 贪心挑大的：[2,7,9,3,1] 先拿最大的 9，再拿不相邻里最大的 7 → 7 和 9 相邻根本不能同拿；即便改成隔一间取一间也只能得 11，漏掉最优的 12，必须逐间比较两种选择。
  • 状态定义成「偷第 i 间的最优」还照抄本文转移：[2,1,1,2] → 语义下 dp[i - 1] 不再是「前 i - 1 间最优」，直接套 max(dp[i - 1], dp[i - 2] + nums[i]) 语义混乱，答案错或需要额外全局取 max。
  • 转移里只允许「隔一间」接续，写成 dp[i] = dp[i - 2] + nums[i]：[2,1,1,2] → 最优解是偷第 1、4 间（隔了两间），强制隔一间只能得 3，正确答案是 4。
  • 数组开头手工特判 dp[0]、dp[1] 时下标写错：n = 1 的 [5] → 访问 nums[1] 直接越界；用 0, 0 起步的滚动写法可整体回避。
  • 空数组未兜底（部分语言或旧接口可能传入）：[] → 手工特判版本访问 nums[0] 崩溃；滚动写法循环不进入自然返回 0。
  • 返回 next 而不是 cur：空数组 → next 未被赋值（或为初始垃圾值），编译报错或返回错误值；循环外应返回 cur。

相似题目

题目 难度 考察点
213. 打家劫舍 II 中等 环形排列：首尾相邻，拆成两次线性 DP 取较大者
337. 打家劫舍 III 中等 树形版本：后序遍历，每个节点返回「偷/不偷」两个状态
740. 删除并获得点数 中等 数值相邻互斥：按值桶计总点数后转化为线性打家劫舍
LCR 089. 打家劫舍 中等 与 198 同题，练习滚动变量的标准写法
LCR 090. 打家劫舍 II 中等 与 213 同题，练习环形拆段的完整推导