0213. House Robber II
=====================
题目信息
--------
:题号: 0213. 打家劫舍 II
:难度: Medium
:主题: 动态规划、环形数组、滚动状态
:原题: `LeetCode 0213 `_
:重点: 首尾房屋相邻、线性递推、环拆线、滚动压缩
题目重述
--------
有一圈房屋,``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++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
static int robLinearTable(const std::vector& nums, int left, int right) {
if (left > right) return 0;
std::vector 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(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& 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& nums) {
const int count = static_cast(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`` 的最优值。于是:
.. code-block:: text
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]``,两个线性子问题的滚动状态如下:
.. list-table::
:header-rows: 1
* - 区间
- 处理顺序
- ``(previous_two, previous_one)`` 的变化
- 结果
* - ``[0,1]``
- 2、3
- ``(0,0) -> (0,2) -> (2,3)``
- 3
* - ``[1,2]``
- 3、2
- ``(0,0) -> (0,3) -> (3,3)``
- 3
``(previous_two, previous_one)`` 保存的是前缀最优金额,而不是最近两间房的金额。比如处理第二个区间的 2 时,
连接前两间的候选是 ``0+2``,不选当前则保留已有的 3。
代码演进与方案选择
~~~~~~~~~~~~~~~~~~~~
``robLinearTable`` 保留完整数组只为展示状态来源,``robLinearRolling`` 删除已经不会再读取的前缀。公共入口只负责处理两个互斥区间,
选择滚动版本作为主解;它不再维护“首房是否已选”的额外标记,因为该信息已经由区间端点表达。
复杂度与边界
~~~~~~~~~~~~
两个区间各扫描至多 ``n`` 间房,主解时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。完整表版本时间同为 ``O(n)``,
额外空间为 ``O(n)``;返回值不计入工作空间。单屋、两屋、全零金额、首尾高额和首尾相等的情况都由单屋分支与环拆分覆盖。