0198. House Robber ================== 题目信息 -------- :题号: 0198. 打家劫舍 :难度: Medium :主题: 动态规划、前缀最优、相邻排斥、滚动状态 :原题: `LeetCode 0198 `_ :重点: 按最后一间选或不选拆分全部方案,再把只依赖两个前缀的 DP 压缩为常数状态 题目重述 -------- 给定非负整数数组 ``nums``,``nums[i]`` 是第 ``i`` 间房屋中的金额。不能选择两间相邻 房屋,返回所有合法选择能取得的最大总金额。 可以不选择任何房屋;只要求最大金额,不需要返回具体房屋下标。 自建示例 -------- .. code-block:: text 输入:nums = [1,2,3,1] 输出:4 选择金额 1 和 3,总计 4。 .. code-block:: text 输入:nums = [2,7,9,3,1] 输出:12 选择 2、9、1。只在每对相邻房屋中选较大者会错过这种跨段组合。 .. code-block:: text 输入:nums = [8] 输出:8 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: int fullPrefixTable(const std::vector& nums) { int size = static_cast(nums.size()); if (size == 0) { return 0; } std::vector best(size + 1, 0); best[1] = nums[0]; for (int houses = 2; houses <= size; ++houses) { best[houses] = std::max( best[houses - 1], best[houses - 2] + nums[houses - 1]); } return static_cast(best[size]); } int rollingPrefixes(const std::vector& nums) { long long two_back = 0; long long one_back = 0; for (int money : nums) { long long take_current = two_back + money; long long current = std::max(one_back, take_current); two_back = one_back; one_back = current; } return static_cast(one_back); } public: int rob(std::vector& nums) { return rollingPrefixes(nums); } }; 题解 ---- 原始搜索是选或不选的决策树 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 对每间房屋都尝试“选择、跳过”,并在选择后跳过下一间,可以枚举全部合法方案。但分支数 随房屋数量指数增长,而且不同选择历史会到达同一个剩余后缀,重复计算它能贡献的最优值。 局部贪心也无法替代搜索。例如在 ``[2,7,9,3,1]`` 中先从前两间选择较大的 7,看似合理, 却会阻止选择 9;全局最优反而选择 2、9、1。当前选择会改变下一位置是否可选,必须保存 足以描述前缀约束的最优状态。 按最后一间拆分全部方案 ~~~~~~~~~~~~~~~~~~~~~~ 定义 ``best[i]`` 为只考虑前 ``i`` 间房屋时的最大金额。对最后一间,也就是数组下标 ``i-1``,任意合法方案恰好属于两类: * 不选最后一间:全部选择位于前 ``i-1`` 间,最优为 ``best[i-1]``; * 选择最后一间:相邻的倒数第二间必须排除,之前只能取前 ``i-2`` 间最优,再加 ``nums[i-1]``。 两类互斥且覆盖全部方案,因此: .. code-block:: text best[i] = max(best[i-1], best[i-2] + nums[i-1]) 边界 ``best[0] = 0`` 表示没有房屋,``best[1] = nums[0]`` 表示单间时选择它最优。金额 非负,所以不需要用负无穷表示“不选任何房屋”。 为什么递推没有丢失具体选择 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 选择最后一间时,前部与它之间隔着未选的倒数第二间,因此任意达到 ``best[i-2]`` 的方案 都能安全与当前房屋组合;不选时,达到 ``best[i-1]`` 的方案也仍合法。两个数值分别是两类 方案可达到的上界,而且上界都有构造,所以取最大值既不低估也不引入相邻冲突。 ``fullPrefixTable`` 按房屋数量从小到大计算,当前依赖都已确定。长度为 ``n+1`` 的数组让 房屋下标与前缀数量分开,避免第一、第二间的负下标边界。 空间如何压缩成两个前缀 ~~~~~~~~~~~~~~~~~~~~~~~~ 计算 ``best[i]`` 后,更早的 ``best[0..i-3]`` 不会再被直接读取。``rollingPrefixes`` 只 维护: * ``one_back``:已处理全部前缀的最优值; * ``two_back``:少一间前缀的最优值。 处理当前金额前,若已处理 ``i`` 间,则 ``one_back = best[i]``、 ``two_back = best[i-1]``。选择当前房屋得到 ``two_back + money``,跳过得到 ``one_back``,两者最大值就是 ``best[i+1]``。 必须先用旧状态算出 ``current``,再执行 ``two_back = one_back``、 ``one_back = current``。若先覆盖 ``two_back``,选择分支会读取 ``best[i]``,等价于允许 当前房屋与前一间同时被选,破坏相邻排斥。 具体状态走读 ~~~~~~~~~~~~ 对 ``[1,2,3,1]``: .. code-block:: text 当前金额 旧 two_back 旧 one_back 选择当前 跳过当前 新最优 1 0 0 1 0 1 2 0 1 2 1 2 3 1 2 4 2 4 1 2 4 3 4 4 第三轮的 4 来自第一间最优 1 加当前 3;第四轮选择当前只能得到 3,所以保留旧前缀最优 4。 空数组时循环不执行并返回初始 0;单间时第一轮比较 0 与该金额,得到单间答案。重复金额、 零金额都不改变位置约束,状态只按下标前缀推进。 方案选择与复杂度 ~~~~~~~~~~~~~~~~ 完整前缀表和滚动方案都只处理每间房屋一次,时间为 ``O(n)``。完整表保存全部前缀答案, 空间 ``O(n)``,适合理解或需要恢复方案时继续扩展;本题只返回最大金额,滚动变量删除不再 使用的历史,额外空间降为 ``O(1)``,因此 ``rollingPrefixes`` 是主解。状态使用 ``long long`` 保存中间和,最终按题目接口转换为 ``int``。