LeetCode 213. House Robber II 环形打家劫舍Go 动态规划解法与源码解析【免费下载链接】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」打家劫舍 II展开在 LeetCode-Go 开源仓库中该题以rob213实现了一套基于滚动变量动态规划的环形街道解法。读完本文你将掌握「环形序列」如何拆解为两个线性区间、如何用 O(1) 辅助空间的 DP 完成求解并能直接复用仓库中的源码与测试用例验证你的理解。题目原文You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place arearranged in a circle.That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected andit will automatically contact the police if two adjacent houses were broken into on the same night.Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonightwithout alerting the police.本题是 198. House Robber打家劫舍的环形加强版。区别仅在于本街道所有房屋围成一圈第一个房屋与最后一个房屋互为邻居因此「首尾不能同时被偷」成为新的约束条件。示例Example 1Input: [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money 2) and then rob house 3 (money 2), because they are adjacent houses.输入[2, 3, 2]时房屋 1 与房屋 3 在环形街道上相邻二者不能同时被偷只能二选一或只偷房屋 2因此最优解为偷房屋 2获得3。Example 2Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money 1) and then rob house 3 (money 3). Total amount you can rob 1 3 4.输入[1, 2, 3, 1]时偷房屋 1价值 1与房屋 3价值 3总价值1 3 4且没有触发相邻警报。题目大意你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。解题思路环形问题拆解为两个线性区间这一题是第 198 题的加强版。不过这次是在一个环形的街道中即最后一个元素和第一个元素是邻居在不触碰警报的情况下问能够窃取的财产的最大值是多少解题思路和第 198 完全一致只需要增加额外的一个转换。由于首尾是相邻的所以在取了第一个房子以后就不能取第 n 个房子那么就在[0, n-1]的区间内找出总价值最多的解然后再[1, n]的区间内找出总价值最多的解两者取最大值即可。环形带来的唯一新约束是「第一个房屋与最后一个房屋互为邻居」因此最优方案只有两种情况不偷最后一个房屋问题退化为在nums[0..n-2]这个线性区间上求解不偷第一个房屋问题退化为在nums[1..n-1]这个线性区间上求解。由于环形上任意「合法偷窃方案」必然属于上述两种情况之一要么不偷 0 号要么不偷 n-1 号所以最终的答案就是这两个线性子问题的最大值。这正是仓库源码中rob213的写法。仓库源码逐行解析LeetCode-Go 仓库中本题的实现位于 213. House Robber II.gopackage 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]) } // 由于首尾是相邻的所以需要对比 [0n-1]、[1n] 这两个区间的最大值 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[start1]) 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 }边界条件处理rob213首先处理三类平凡情况n 0空街道无房可偷直接返回0n 1只有一间房返回该房金额nums[0]n 2两间房首尾相邻但只有两间时互为唯一邻居最多只能偷其中一间返回max(nums[0], nums[1])。对于n 3的情况才进入环形区间拆解逻辑。环形拆解两个区间取最大值return max(rob213_1(nums, 0, n-2), rob213_1(nums, 1, n-1))rob213_1(nums, 0, n-2)闭区间[0, n-2]即「排除最后一个房屋」保证首尾不相邻rob213_1(nums, 1, n-1)闭区间[1, n-1]即「排除第一个房屋」同样保证首尾不相邻。最终取两者较大值即为环形街道上的最优偷窃金额。这一「环形转双线性区间」的套路也是环形 DP 类问题如环形最大子数组和的通用降维手段。线性区间内的滚动 DProb213_1在线性区间[start, end]内执行与第 198 题完全相同的状态转移preMax截至前前个房屋的最优解对应状态dp[i-2]curMax截至上一个房屋的最优解对应状态dp[i-1]。状态转移方程为curMax max(curMax, nums[i] preMax)即当前位置的最优解要么「不偷当前房屋」沿用dp[i-1]要么「偷当前房屋」累加dp[i-2] nums[i]。每次迭代先将旧curMax暂存到tmp再更新curMax最后把tmp赋给preMax实现两个变量的滚动迭代。这与 198. House Robber.go 中rob198_1的滚动变量优化写法本质一致只是rob198_1从整个数组的0..n-1迭代而rob213_1被抽象成了可指定start、end的通用子函数从而能被环形拆解复用两次。复杂度分析时间复杂度O(n)。两次线性扫描每次扫描O(n)总复杂度仍为O(n)空间复杂度O(1)。仅使用preMax、curMax、tmp等常数个变量未额外申请与n相关的辅助数组。相比经典的dp[]数组版本如 198 题解法一滚动变量版将空间从O(n)压缩到O(1)同时由于两次扫描只遍历数组一遍各一次时间上没有任何额外开销。测试用例与验证仓库为本题提供了完整的表驱动测试见 213. House Robber II_test.go。测试覆盖了以下关键场景输入预期输出覆盖点[]0空数组边界[0, 0]0两间金额为 0 的房屋[5]5单间房屋[2, 3, 2]3环形首尾相邻约束Example 1[1, 2, 3, 1]4常规环形场景Example 2测试函数Test_Problem213通过para213/ans213结构体组织输入输出对循环调用rob213(p.one)并打印结果属于该仓库统一的表驱动测试风格。整个仓库通过 gotest.sh 以go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式对全部题目进行覆盖率收集本题与其他题解一样被纳入统一的测试与覆盖率体系。总结LeetCode 213 题「打家劫舍 II」的核心考点是环形序列的线性化拆解利用「首尾不能同时偷」这一约束将环形问题等价地拆成[0, n-2]与[1, n-1]两个线性子问题再分别套用第 198 题的滚动变量 DP 求解最终取两者最大值。该解法时间O(n)、空间O(1)是环形 DP 问题最具代表性的入门范例掌握后可以平滑迁移到其他「首尾相连」的场景。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/10 19:08:22 · 阅读 1.2k LeetCode 213. House Robber II 环形打家劫舍：Go 动态规划解法与源码解析
LeetCode 213. House Robber II 环形打家劫舍Go 动态规划解法与源码解析【免费下载链接】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」打家劫舍 II展开在 LeetCode-Go 开源仓库中该题以rob213实现了一套基于滚动变量动态规划的环形街道解法。读完本文你将掌握「环形序列」如何拆解为两个线性区间、如何用 O(1) 辅助空间的 DP 完成求解并能直接复用仓库中的源码与测试用例验证你的理解。题目原文You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place arearranged in a circle.That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected andit will automatically contact the police if two adjacent houses were broken into on the same night.Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonightwithout alerting the police.本题是 198. House Robber打家劫舍的环形加强版。区别仅在于本街道所有房屋围成一圈第一个房屋与最后一个房屋互为邻居因此「首尾不能同时被偷」成为新的约束条件。示例Example 1Input: [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money 2) and then rob house 3 (money 2), because they are adjacent houses.输入[2, 3, 2]时房屋 1 与房屋 3 在环形街道上相邻二者不能同时被偷只能二选一或只偷房屋 2因此最优解为偷房屋 2获得3。Example 2Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money 1) and then rob house 3 (money 3). Total amount you can rob 1 3 4.输入[1, 2, 3, 1]时偷房屋 1价值 1与房屋 3价值 3总价值1 3 4且没有触发相邻警报。题目大意你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。解题思路环形问题拆解为两个线性区间这一题是第 198 题的加强版。不过这次是在一个环形的街道中即最后一个元素和第一个元素是邻居在不触碰警报的情况下问能够窃取的财产的最大值是多少解题思路和第 198 完全一致只需要增加额外的一个转换。由于首尾是相邻的所以在取了第一个房子以后就不能取第 n 个房子那么就在[0, n-1]的区间内找出总价值最多的解然后再[1, n]的区间内找出总价值最多的解两者取最大值即可。环形带来的唯一新约束是「第一个房屋与最后一个房屋互为邻居」因此最优方案只有两种情况不偷最后一个房屋问题退化为在nums[0..n-2]这个线性区间上求解不偷第一个房屋问题退化为在nums[1..n-1]这个线性区间上求解。由于环形上任意「合法偷窃方案」必然属于上述两种情况之一要么不偷 0 号要么不偷 n-1 号所以最终的答案就是这两个线性子问题的最大值。这正是仓库源码中rob213的写法。仓库源码逐行解析LeetCode-Go 仓库中本题的实现位于 213. House Robber II.gopackage 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]) } // 由于首尾是相邻的所以需要对比 [0n-1]、[1n] 这两个区间的最大值 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[start1]) 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 }边界条件处理rob213首先处理三类平凡情况n 0空街道无房可偷直接返回0n 1只有一间房返回该房金额nums[0]n 2两间房首尾相邻但只有两间时互为唯一邻居最多只能偷其中一间返回max(nums[0], nums[1])。对于n 3的情况才进入环形区间拆解逻辑。环形拆解两个区间取最大值return max(rob213_1(nums, 0, n-2), rob213_1(nums, 1, n-1))rob213_1(nums, 0, n-2)闭区间[0, n-2]即「排除最后一个房屋」保证首尾不相邻rob213_1(nums, 1, n-1)闭区间[1, n-1]即「排除第一个房屋」同样保证首尾不相邻。最终取两者较大值即为环形街道上的最优偷窃金额。这一「环形转双线性区间」的套路也是环形 DP 类问题如环形最大子数组和的通用降维手段。线性区间内的滚动 DProb213_1在线性区间[start, end]内执行与第 198 题完全相同的状态转移preMax截至前前个房屋的最优解对应状态dp[i-2]curMax截至上一个房屋的最优解对应状态dp[i-1]。状态转移方程为curMax max(curMax, nums[i] preMax)即当前位置的最优解要么「不偷当前房屋」沿用dp[i-1]要么「偷当前房屋」累加dp[i-2] nums[i]。每次迭代先将旧curMax暂存到tmp再更新curMax最后把tmp赋给preMax实现两个变量的滚动迭代。这与 198. House Robber.go 中rob198_1的滚动变量优化写法本质一致只是rob198_1从整个数组的0..n-1迭代而rob213_1被抽象成了可指定start、end的通用子函数从而能被环形拆解复用两次。复杂度分析时间复杂度O(n)。两次线性扫描每次扫描O(n)总复杂度仍为O(n)空间复杂度O(1)。仅使用preMax、curMax、tmp等常数个变量未额外申请与n相关的辅助数组。相比经典的dp[]数组版本如 198 题解法一滚动变量版将空间从O(n)压缩到O(1)同时由于两次扫描只遍历数组一遍各一次时间上没有任何额外开销。测试用例与验证仓库为本题提供了完整的表驱动测试见 213. House Robber II_test.go。测试覆盖了以下关键场景输入预期输出覆盖点[]0空数组边界[0, 0]0两间金额为 0 的房屋[5]5单间房屋[2, 3, 2]3环形首尾相邻约束Example 1[1, 2, 3, 1]4常规环形场景Example 2测试函数Test_Problem213通过para213/ans213结构体组织输入输出对循环调用rob213(p.one)并打印结果属于该仓库统一的表驱动测试风格。整个仓库通过 gotest.sh 以go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式对全部题目进行覆盖率收集本题与其他题解一样被纳入统一的测试与覆盖率体系。总结LeetCode 213 题「打家劫舍 II」的核心考点是环形序列的线性化拆解利用「首尾不能同时偷」这一约束将环形问题等价地拆成[0, n-2]与[1, n-1]两个线性子问题再分别套用第 198 题的滚动变量 DP 求解最终取两者最大值。该解法时间O(n)、空间O(1)是环形 DP 问题最具代表性的入门范例掌握后可以平滑迁移到其他「首尾相连」的场景。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考