0213. House Robber II¶
题目信息¶
- 题号:
打家劫舍 II
- 难度:
Medium
- 主题:
动态规划、环形数组、滚动状态
- 原题:
- 重点:
首尾房屋相邻、线性递推、环拆线、滚动压缩
题目重述¶
有一圈房屋,nums[i] 是第 i 间房中的金额。选择一间房会得到其金额,但相邻两间不能在同一晚同时选择;
由于房屋首尾相接,第 0 间和最后一间也算相邻。返回不触发警报时能够得到的最大金额,不需要返回具体的房屋下标。
房屋数量在 [1,100],金额为非负整数。输入数组只读;只有一间房时不存在第二间房与它相邻,答案就是这间房的金额。
自建示例¶
nums = [8,1,1,8] 返回 9。把数组错误地当成直线会同时选择两个 8 得到 16;在圆环中只能选择一端的 8,
再配一间不相邻的小房屋。
nums = [2,3,2] 返回 3。第 0 间和第 2 间虽然在数组中不相邻,却在圆环中相邻,所以不能同时选择。
nums = [5] 返回 5;nums = [2,7] 返回 7,两间房互相相邻时只能取金额较大的一间。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
static int robLinearTable(const std::vector<int>& nums, int left, int right) {
if (left > right) return 0;
std::vector<int> dp(right - left + 1, 0);
dp[0] = nums[left];
if (left == right) return dp[0];
dp[1] = std::max(nums[left], nums[left + 1]);
for (int index = 2; index < static_cast<int>(dp.size()); ++index) {
dp[index] = std::max(dp[index - 1],
dp[index - 2] + nums[left + index]);
}
return dp.back();
}
static int robLinearRolling(const std::vector<int>& nums, int left, int right) {
int previous_two = 0;
int previous_one = 0;
for (int index = left; index <= right; ++index) {
const int current = std::max(previous_one,
previous_two + nums[index]);
previous_two = previous_one;
previous_one = current;
}
return previous_one;
}
public:
int rob(std::vector<int>& nums) {
const int count = static_cast<int>(nums.size());
if (count == 1) return nums[0];
return std::max(robLinearRolling(nums, 0, count - 2),
robLinearRolling(nums, 1, count - 1));
}
};
题解¶
线性房屋的最后一步¶
先忽略首尾相邻,把房屋看成一条线。逐间枚举“选或不选”当然覆盖全部方案,但搜索树有 O(2^n) 个叶子。
固定处理到下标 i 的最优值时,最后一间只有两个互斥去向:不选它,继承 i-1 的最优值;选它,则 i-1 不能选,
只能接上 i-2 的最优值。于是:
best[i] = max(best[i - 1], best[i - 2] + nums[i])
这个递推的关键不是金额的具体组合,而是“同一个前缀只保留最大金额”已经足够支配后续选择。金额非负只让空前缀可以用 0 初始化。
环形约束的唯一额外信息¶
线性递推会把第 0 间和最后一间同时纳入。圆环的特殊边只有这一条,因此按第 0 间是否选择分成两个互斥覆盖的区间:
不选第 0 间:在
[1,n-1]上运行线性 DP;选择第 0 间:最后一间必不能选,在
[0,n-2]上运行线性 DP。
每个合法方案恰好落入其中一个分支,两个区间内部已经是普通线性问题。这样把“是否选过首房”的历史状态编码进边界, 避免让每个 DP 单元额外携带一个布尔维度。
滚动状态与更新顺序¶
robLinearTable 用完整数组展示线性递推;但计算新项只读取前两项。robLinearRolling 在处理 index 前保持:
previous_one是区间[left,index-1]的最优值;previous_two是区间[left,index-2]的最优值;选择当前房屋的候选为
previous_two + nums[index],跳过当前的候选为previous_one。
必须先用两个旧值算出 current,再执行 previous_two = previous_one、previous_one = current。若提前覆盖旧值,
下一轮就会把相邻两间房错误地当成可同时选择。
状态走读¶
对 nums=[2,3,2],两个线性子问题的滚动状态如下:
区间 |
处理顺序 |
|
结果 |
|---|---|---|---|
|
2、3 |
|
3 |
|
3、2 |
|
3 |
(previous_two, previous_one) 保存的是前缀最优金额,而不是最近两间房的金额。比如处理第二个区间的 2 时,
连接前两间的候选是 0+2,不选当前则保留已有的 3。
代码演进与方案选择¶
robLinearTable 保留完整数组只为展示状态来源,robLinearRolling 删除已经不会再读取的前缀。公共入口只负责处理两个互斥区间,
选择滚动版本作为主解;它不再维护“首房是否已选”的额外标记,因为该信息已经由区间端点表达。
复杂度与边界¶
两个区间各扫描至多 n 间房,主解时间复杂度为 O(n),额外空间为 O(1)。完整表版本时间同为 O(n),
额外空间为 O(n);返回值不计入工作空间。单屋、两屋、全零金额、首尾高额和首尾相等的情况都由单屋分支与环拆分覆盖。