LeetCode-Go 题解：213. House Robber II 环形打家劫舍的动态规划解法

LeetCode-Go 题解：213. House Robber II 环形打家劫舍的动态规划解法

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇围绕 LeetCode 第 213 题 House Robber II 展开，讲解环形街道约束下的"打家劫舍"问题：如何利用环形拆分为两个线性区间的技巧，复用经典 198 题的滚动数组动态规划，在 O(n) 时间、O(1) 空间内求出不触发警报的最大偷窃金额。文中代码与测试均取自 LeetCode-Go 仓库的真实实现（213. House Robber II.go 与 213. House Robber II_test.go），可直接复制运行验证。

一、题目回顾

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。与 198 题不同的是，这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1：

输入: [2,3,2] 输出: 3 解释: 你不能先偷 1 号房屋（金额 = 2），然后再偷 3 号房屋（金额 = 2），因为它们是相邻的房屋。

示例 2：

输入: [1,2,3,1] 输出: 4 解释: 你可以先偷 1 号房屋（金额 = 1），然后再偷 3 号房屋（金额 = 3），偷窃到的最高金额 = 1 + 3 = 4。

示例 1 恰好体现了环形约束的核心：在直线街道上，[2,3,2]可以偷 2 + 2 = 4；但在环形街道上，1 号与 3 号相邻，二者只能取其一，因此答案是 max(2, 3) = 3。

二、题意拆解：环形约束的本质

原文档 0213.House-Robber-II.md 的 Problem Summary 明确了三点关键约束：

1. 环形排列：所有房屋围成一圈，第一个房屋与最后一个房屋互为邻居；
2. 相邻互斥：同一晚不能偷窃任意两间相邻的房屋，否则触发警报；
3. 金额非负：数组元素为非负整数，无需处理负数干扰。

环形约束只引入了一个额外限制：首尾房屋不能同时被偷。除此之外，中间任意两间相邻房屋的互斥关系与直线街道完全一致。因此，本题的解题思路与第 198 题完全一致，只需要增加一个"拆环"的转换。

三、解题思路：把环形街道拆成两个线性区间

原文档给出的核心思路非常精炼：由于首尾是相邻的，所以在取了第一个房子以后就不能取第 n 个房子；那么就在[0, n-1]的区间内找出总价值最多的解，再在[1, n]的区间内找出总价值最多的解，两者取最大值即可。

用 0 起始索引精确表述，就是把长度为 n 的环拆成两个不跨越首尾边界的线性区间：

• 区间 A：[0, n-2]——包含 0 号房屋，不包含 n-1 号房屋，代表"偷了第一间房"的方案空间；
• 区间 B：[1, n-1]——不包含 0 号房屋，可以包含 n-1 号房屋，代表"不偷第一间房"的方案空间。

完备性论证：任意一个不触发警报的合法偷窃方案，0 号房屋只有"偷"与"不偷"两种状态。若偷 0 号房屋，由于首尾相邻，n-1 号房屋必然不能偷，方案完全落在区间 A 内；若不偷 0 号房屋，方案完全落在区间 B 内。因此，两个区间最优解的最大值，就是全局最优解，不存在遗漏。

注：文档正文写作[0, n-1]与[1, n]，这是以 1 为起始的表述习惯；仓库源码在 0 起始索引下实现为[0, n-2]与[1, n-1]（见 213. House Robber II.go），两者是同一件事。

四、线性区间内的动态规划递推

对于任意线性区间[start, end]，问题退化为经典的 198 题。设dp[i]表示偷窃nums[0...i]（相对该区间）所能获得的最大金额，递推关系为：

dp[i] = max(dp[i-1], nums[i] + dp[i-2])

含义是：对于第 i 间房，要么不偷（继承前 i-1 间的最优值dp[i-1]），要么偷（获得nums[i]加上前 i-2 间的最优值dp[i-2]，因为第 i-1 间不能偷）。

由于dp[i]只依赖dp[i-1]与dp[i-2]，可以进一步做滚动数组优化：只用preMax与curMax两个变量滚动迭代，把空间复杂度压到 O(1)。这正是仓库中rob213_1的实现方式，也与 198 题源码中的空间优化版本一脉相承（可对比 198. House Robber.go 中的rob198_1）。

五、完整 Go 实现

仓库源码 213. House Robber II.go 给出了完整实现：

package leetcode func rob213(nums []int) int { n := len(nums) if n == 0 { return 0 } if n == 1 { return nums[0] } if n == 2 { return max(nums[0], nums[1]) } // 由于首尾是相邻的，所以需要对比 [0，n-1]、[1，n] 这两个区间的最大值 return max(rob213_1(nums, 0, n-2), rob213_1(nums, 1, n-1)) } func rob213_1(nums []int, start, end int) int { preMax := nums[start] curMax := max(preMax, nums[start+1]) for i := start + 2; i <= end; i++ { tmp := curMax curMax = max(curMax, nums[i]+preMax) preMax = tmp } return curMax } func max(a int, b int) int { if a > b { return a } return b }

逐段讲解：

1. 入口函数rob213：先处理边界情况，再对两个区间分别求解并取最大值；
2. 区间求解函数rob213_1：对区间内前两个元素初始化preMax = nums[start]（前 1 间的最优值）、curMax = max(preMax, nums[start+1])（前 2 间的最优值），然后从start+2滚动迭代到end；
3. 状态转移：curMax = max(curMax, nums[i]+preMax)对应dp[i] = max(dp[i-1], nums[i] + dp[i-2])；迭代前用tmp暂存旧curMax，再将其赋给preMax，完成变量滚动；
4. 辅助函数max：该题解文件内自带的取较大值函数（仓库 213 源码为自包含实现，未依赖外部包）。

六、边界情况与复杂度分析

rob213开头的三个分支是环形拆分成立的前提，缺一不可：

对于n >= 3，两个区间[0, n-2]与[1, n-1]均至少包含两个元素，rob213_1的初始化逻辑安全。

复杂度结论：每个区间各遍历一次，总时间复杂度 O(n)；全程只使用常量个变量，空间复杂度 O(1)。这也是环形拆分方案优于"直接枚举首尾是否被偷后跑完整 DP 数组"的原因——无需任何额外数组即可完成求解。

七、测试用例验证

仓库配套的 213. House Robber II_test.go 采用表格驱动测试，覆盖了本题全部关键分支：

其中[2, 3, 2]这一用例直接检验了"拆环"的正确性：若误用直线解法会得到 4，而正确结果是通过max(rob213_1(nums, 0, 1), rob213_1(nums, 1, 2)) = max(3, 3) = 3得到的。测试函数会在终端打印每个输入的输出值，便于人工核对中间结果。

八、与 198. House Robber 的横向对比

本题是第 198 题的加强版，两者在仓库中同属leetcode包，可以对照阅读 198. House Robber.go：

198 题的仓库实现提供了三种解法——数组 DP（rob198）、滚动变量优化（rob198_1）以及奇偶位模拟（rob）。213 题选用的正是与rob198_1同款的滚动数组思路，并把它封装成rob213_1(nums, start, end)以支持任意区间求解，体现了"基础题解法 + 一次额外转换"的解题范式：先掌握线性版本的状态定义与转移方程，再针对环形结构做区间拆解。

九、总结

House Robber II 是动态规划中"结构变换"类题目的经典代表：

1. 识别约束：环形街道的唯一增量约束是"首尾相邻、不可兼得"；
2. 拆环为线：按是否偷 0 号房屋，将环完备地拆为[0, n-2]与[1, n-1]两个线性区间，取两区间最优值的最大值；
3. 复用递推：在每个区间内沿用 198 题的dp[i] = max(dp[i-1], nums[i]+dp[i-2])，并以滚动变量实现 O(1) 空间；
4. 严守边界：n == 0 / 1 / 2三种短输入必须先行返回，保证区间初始化不越界。

参考阅读：题目文档见 website/content.en/ChapterFour/0200~0299/0213.House-Robber-II.md，对应题目目录leetcode/0213.House-Robber-II/下存放源码与测试，其前置基础题 198 位于leetcode/0198.House-Robber/。掌握本题后，可进一步挑战 337. House Robber III（二叉树形态），体会同一递推思想在不同数据结构上的迁移。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go