213. 打家劫舍 II（中等）

Blind 75 › 213. 打家劫舍 II（中等） （第 3 章）
文章工具

题目

给定一个非负整数数组，表示若干户房屋里的金额。这些房屋排成一圈：也就是说，第 1 户与最后一户也是邻居。

如果任意两户相邻（包括首尾这一对）都同时被你光顾，就会触发警报。在不报警的前提下，问：今晚最多能拿到多少钱？

换句话说：在一串首尾相接的数字里选若干项，使得选中的两项都不相邻，求选中项之和的最大值。

自造示例：[3,2,3,1] → 6。最优是偷第 1 户和第 3 户：3 + 3 = 6；其余选择要么首尾或相邻冲突，要么金额更小。

再如只有一户时没有环冲突：[5] → 5。

约束：1 ≤ nums.length ≤ 100；0 ≤ nums[i] ≤ 1000。

思路

一句话：环形只比一条直线多一条“首尾不能同时偷”的限制；把环剪成两段，分别求两段直线上的最优值，再取较大者。

先想最直白的做法：枚举所有“偷 / 不偷”的子集，再逐个检查有没有相邻。共有 2n 种子集，即使用位运算判断冲突也要爆掉。

再回想直线版“打家劫舍”怎么解：走到第 i 户，只有两种选择——

  • 偷第 i 户：第 i-1 户不能偷，收益是 dp[i-2] + nums[i]；
  • 不偷第 i 户：收益沿用 dp[i-1]。

于是 dp[i] = max(dp[i-1], dp[i-2] + nums[i])；因为只依赖前两项，可以用两个滚动变量把空间压到 O(1)。

关键观察：成环以后，最优方案不可能同时偷第 1 户和最后一户——它俩相邻，同偷一定报警。既然“首尾互斥”，就可以按二选一分类：

  • 不要最后一户：问题退化为在 nums[0..n-2] 上求直线版；
  • 不要第一户：问题退化为在 nums[1..n-1] 上求直线版。

两类合起来覆盖了所有合法方案，所以取两者的最大值就是答案。唯一要单独处理的是 n == 1：此时“第一户”和“最后一户”是同一户，不存在环冲突，直接返回 nums[0]。

解法

把直线版打包成一个辅助函数 robLine(lo, hi)，内部滚两个变量：

  1. 若数组只有 1 个数，直接返回该数。
  2. 分别计算 robLine(0, n-2) 与 robLine(1, n-1)。
  3. robLine 初始化 prev2 = prev1 = 0，分别代表 dp[i-2]、dp[i-1]；每走一步算出 cur = max(prev1, prev2 + nums[i])，再滚动。
  4. 返回 max(两段结果)。

以 [3,2,3,

🔒

本篇为付费内容

您已阅读试读部分，购买后即可解锁全文。

⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。