LeetCode-Go 题解精讲198. House Robber 打家劫舍 —— 动态规划状态转移方程与三种 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 198. House Robber 题解为核心完整解析「打家劫舍」这道经典一维动态规划题目。文中不仅复述题目要求与核心状态转移方程dp[i] max(dp[i-1], nums[i] dp[i-2])更结合仓库内 198. House Robber.go 的真实实现逐一讲解标准 DP、滚动变量空间优化、奇偶位模拟三种写法的原理与代码。读完本文你将掌握这类「相邻不可选」线性 DP 问题的通用建模方法并能在实际面试中根据空间要求灵活切换实现。题目描述You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that 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.Example 1:Input: [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.Example 2:Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money 2), rob house 3 (money 9) and rob house 5 (money 1). Total amount you can rob 2 9 1 12.题目大意你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。解题思路总览这道题的约束只有一个不能同时偷相邻的两间房。因此对每个位置只有「偷」与「不偷」两种决策且两种决策相互制约天然符合动态规划的建模方式。仓库 README 明确指出本题「可以用 DP 来解答也可以用找规律的方法来解答」对应的 Go 源码中提供了三种实现函数名思路时间/空间复杂度rob198标准 DP数组缓存每个位置的最优值O(n) / O(n)rob198_1DP 滚动变量只保留前两个状态O(n) / O(1)rob奇偶位模拟找规律动态维护两个游标O(n) / O(1)三者共用同一组测试用例位于 198. House Robber_test.go实现细节如下。解法一标准动态规划数组缓存状态状态定义与转移方程DP 的状态定义是dp[i]代表抢nums[0,i]这个区间内房子的最大值。对于第i间房只有两种选择不抢第i间收益为dp[i-1]抢第i间由于不能抢相邻房间收益为nums[i] dp[i-2]。于是得到核心状态转移方程dp[i] max(dp[i-1], nums[i] dp[i-2])边界条件需要单独处理前两个元素dp[0] nums[0]只有一间房直接抢dp[1] max(nums[1], nums[0])两间房只能二选一。仓库源码实现House Robber.go 中rob198的完整实现如下// 解法一 DP func rob198(nums []int) int { n : len(nums) if n 0 { return 0 } if n 1 { return nums[0] } // dp[i] 代表抢 nums[0...i] 房子的最大价值 dp : make([]int, n) dp[0], dp[1] nums[0], max(nums[1], nums[0]) for i : 2; i n; i { dp[i] max(dp[i-1], nums[i]dp[i-2]) } return dp[n-1] } func max(a int, b int) int { if a b { return a } return b }注意两个细节源码在包内自行定义了max辅助函数198. House Robber.go不依赖外部依赖可直接运行入参为空数组时直接返回0长度为 1 时直接返回nums[0]这两个边界分支与测试用例一一对应。转移方程推演以[1, 2, 3, 1]为例逐步填充dp数组inums[i]计算过程dp[i]01初始值dp[0] nums[0]112初始值max(nums[1], nums[0]) max(2, 1)223max(dp[1], nums[2]dp[0]) max(2, 31)431max(dp[2], nums[3]dp[1]) max(4, 12)4最终结果dp[3] 4与题目 Example 1 一致。再以[2, 7, 9, 3, 1]验证inums[i]计算过程dp[i]02dp[0] 2217max(7, 2)729max(7, 92)1133max(11, 37)1141max(11, 111)12结果为12与题目 Example 2 一致。可见该方程正确刻画了「相邻不相容」的约束。解法二滚动变量优化O(1) 空间从转移方程可以发现dp[i]只依赖dp[i-1]与dp[i-2]两个历史状态前面的状态一旦被消费就不再需要。因此可以用两个临时变量滚动迭代把辅助空间从 O(n) 压缩到 O(1)。这正是 README 中提到的「可以优化迭代的过程用两个临时变量来存储中间结果以节约辅助空间」。House Robber.go 中rob198_1的实现// 解法二 DP 优化辅助空间把迭代的值保存在 2 个变量中 func rob198_1(nums []int) int { n : len(nums) if n 0 { return 0 } curMax, preMax : 0, 0 for i : 0; i n; i { tmp : curMax curMax max(curMax, nums[i]preMax) preMax tmp } return curMax }其中curMax等价于dp[i]即抢到当前位置的最大收益preMax等价于dp[i-1]供下一轮计算nums[i] 上一个上一轮时使用每次迭代先用tmp暂存旧的curMax再更新curMax最后把tmp赋给preMax完成状态滚动。以[1, 2, 3, 1]推演一轮itmp旧 curMaxcurMax 更新preMax00max(0, 10) 1011max(1, 20) 2122max(2, 31) 4234max(4, 12) 44最终curMax 4。由于全程只维护两个整型变量空间复杂度降为 O(1)且不需要像解法一那样在循环前单独处理n 1的分支curMax的初值0天然兼容空数组与单元素场景。解法三奇偶位模拟找规律第三种实现来自对问题规律的观察既然不能偷相邻房屋那么合法的偷窃序列必然是「隔一家偷一家」的某种交错组合。源码注释将其描述为「模拟」a偶数位下标i % 2 0上的最大收益记录b奇数位下标i % 2 1上的最大收益记录。House Robber.go 的完整实现// 解法三 模拟 func rob(nums []int) int { // a 对于偶数位上的最大值的记录 // b 对于奇数位上的最大值的记录 a, b : 0, 0 for i : 0; i len(nums); i { if i%2 0 { a max(anums[i], b) } else { b max(a, bnums[i]) } } return max(a, b) }需要特别说明的是这不是简单粗暴的「偶数位求和 vs 奇数位求和」每一步都在「延续当前奇偶链anums[i]或bnums[i]」与「切换到另一条链b或a」之间取最大值因此它能正确处理[2, 7, 9, 3, 1]这类需要跨位跳跃偷 2、9、1的情况。以[2, 7, 9, 3, 1]推演i奇偶a 更新b 更新0偶max(02, 0) 201奇2max(2, 07) 72偶max(29, 7) 1173奇11max(11, 73) 104偶max(111, 11) 1211最终max(a, b) 12与标准 DP 结论一致。该写法代码最精简同样只需要 O(1) 辅助空间。测试用例与验证仓库为本题编写了表驱动测试位于 198. House Robber_test.go。测试覆盖了空数组、单元素、两元素以及题目给出的两个示例且三个实现共用同一组断言输入nums期望输出[]0[5]5[1, 2]2[1, 2, 3, 1]4[2, 7, 9, 3, 1]12测试中每组用例分别调用rob198、rob198_1与rob并逐一比对结果198. House Robber_test.go三者输出不一致即触发t.Fatalf。从测试覆盖可以看出空数组返回 0无房可抢单元素返回该元素本身两元素时只能二选一取较大者多元素场景下三种解法结果严格一致互相印证正确性。三种解法对比与选型建议实现状态载体时间复杂度空间复杂度适用场景rob198标准 DPdp[]数组O(n)O(n)思路最直观便于讲解与推导适合作为面试第一步rob198_1滚动变量curMax/preMax两个变量O(n)O(1)面试追问「能否优化空间」时的标准答案rob奇偶位模拟a/b两个变量O(n)O(1)代码最精简体现找规律思路但可读性略低于 DP三者时间复杂度相同均为 O(n)n 为房屋数量区别集中在空间占用与代码表达上。实际面试建议从解法一讲起再自然过渡到解法二解法三可作为补充思路展示。延伸打家劫舍系列题目「相邻不可选」的模型在 LeetCode 上还有多个变体均可在本仓库找到对应题解213. House Robber II环形街道首尾相邻核心技巧是把环拆成「不抢第一间」与「不抢最后一间」两个线性子问题见 0213.House-Robber-II337. House Robber III二叉树结构父节点与子节点不能同时偷状态升级为树形 DP在每个节点上同时维护「偷 / 不偷」两种收益见 0337.House-Robber-III。掌握本题的一维 DP 建模是理解上述变体的基础无论是环、树还是带权约束的变体核心都是「对每个决策点维护一组互相排斥的状态并用 max 聚合最优子结构」。总结LeetCode 198 题「打家劫舍」是最经典的一维动态规划入门题。本文以 198. House Robber README 为骨架结合 198. House Robber.go 的三种实现与 198. House Robber_test.go 的测试用例完整覆盖了状态定义、状态转移方程dp[i] max(dp[i-1], nums[i] dp[i-2])、边界处理、空间优化与找规律解法。关键要点可归纳为三点建模每个位置只有偷/不偷两种决策用dp[i]表示前缀区间的最优收益优化转移方程只依赖前两个状态滚动变量可将空间从 O(n) 降到 O(1)验证仓库测试覆盖空数组、单元素、双元素与示例用例三种实现互相印证可直接在本地通过go test运行验证项目根目录 gotest.sh 提供了批量测试脚本。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考