LeetCode 198 House Robber 题解：打家劫舍动态规划的决策推导与 O(1) 空间优化

LeetCode 198 House Robber 题解打家劫舍动态规划的决策推导与 O(1) 空间优化【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以 leetcode 仓库中 problems/198.house-robber.en.md及其中文版 problems/198.house-robber.md为核心深入讲解「打家劫舍」这一经典入门级动态规划Dynamic Programming问题的完整解题链路从抢 / 不抢的二元决策出发推导状态转移方程再到基于滚动变量的 O(1) 空间优化并给出 JS / C / Python / Java 四种语言的可运行实现。读完本文你不仅能独立 AC 本题还能掌握一套适用于线性序列 相邻约束类 DP 问题的通用分析范式。题目描述你是一个专业小偷计划偷窃沿街的房屋。每间房内都藏有一定金额的现金以非负整数数组nums表示nums[i]为第 i 间房屋的金额影响偷窃的唯一制约因素是相邻房屋装有相互连通的防盗系统若同一晚闯入两间相邻房屋系统会自动报警。给定数组nums计算在不触发警报的前提下一夜之内能够偷窃到的最高金额。示例 1输入[1,2,3,1] 输出4 解释偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。 偷窃到的最高金额 1 3 4。示例 2输入[2,7,9,3,1] 输出12 解释偷窃 1 号房屋金额 2偷窃 3 号房屋金额 9接着偷窃 5 号房屋金额 1。 偷窃到的最高金额 2 9 1 12。数据约束出自中文版题解0 nums.length 1000 nums[i] 400前置知识动态规划Dynamic Programming建议先通读仓库中的专题文章 thinkings/dynamic-programming.md其中系统讲解了记忆化递归、最优子结构、无后效性以及状态定义是动态规划的核心这一方法论与本题的推导思路一脉相承。解题思路本质是抢还是抢不抢的决策这是一道非常典型且简单的动态规划问题但它的价值在于帮助建立对 DP 的直觉。学 DP 时常遇到两个高频疑问为什么别人的 DP 解可以写得那么简洁为什么不用 dp 数组也能搞定为什么爬楼梯Climbing Stairs问题可以用斐波那契数列Fibonacci Numbers的思想解决本题正好同时回答了这两个问题。和其他简单 DP 问题一样我们本质上是在解决一个决策问题对于第 i 间房子我们抢还是不抢而判断标准就是哪种选择带来的总价值更大。决策一抢第 i 间房子如果抢第 i 间房子那么第i-1间房子不能抢否则会触发警铃因此当前收益为nums[i] dp[i - 2]决策二不抢第 i 间房子如果不抢第 i 间房子那么第i-1间房子可以抢也可以不抢直接继承前一个子问题的最优解即可dp[i - 1]这里的dp即子问题dp[i]表示考虑前 i 间房子在满足约束下能偷到的最大金额。状态转移方程由于我们总是希望收益更大取两者最大值即得到状态转移方程dp[i] Math.max(dp[i - 2] nums[i - 2], dp[i - 1])说明为了计算方便令dp[0]和dp[1]都等于 0此时dp[i]实际上对应的是nums[i - 2]这一项。这个错位设计让数组索引与房子编号解耦避免处理边界时写大量分支判断。上述决策过程可以用下图直观表示注意状态沿数组从左到右推进每次只依赖前两个状态从图中可以观察到一个关键事实计算 dp[i] 时我们真正需要的只有 dp[i-1] 和 dp[i-2]。例如要计算dp[6]只需dp[5]与dp[4]dp[3]、dp[2]等更早的状态都不再需要保留在内存中。这正是滚动变量滚动数组优化的切入点。仓库中 assets/drawio/198.house-robber.drawio 保留了当年绘制该状态转移图解的可编辑 draw.io 源文件便于读者复刻与二次演绎。空间优化从 O(n) 到 O(1)基于只依赖前两个状态的观察可以用两个变量a、b代替整个 dp 数组将空间复杂度从 O(n) 降到 O(1)let a 0; // 相当于 dp[i-2] let b 0; // 相当于 dp[i-1] for (let i 0; i nums.length; i) { const temp b; b Math.max(a nums[i], b); // 抢 nums[i]a nums[i]vs 不抢b a temp; // 状态滚动前移 } return b;逐行解读这段代码初始化a 0、b 0对应题解中dp[0] dp[1] 0的错位约定每轮迭代b Math.max(a nums[i], b)就是状态转移方程的即时版本a nums[i]对应抢当前房子b对应不抢当前房子temp暂存旧的b随后a temp实现dp[i-1]向dp[i-2]的滑动为下一轮计算做准备循环结束后b即全局最优解。这种只需要最近几个状态就滚动压缩的优化手段在 DP 问题中非常普遍斐波那契、爬楼梯等一维线性 DP 均适用是必须掌握的通用技能。补充动态规划本质上是递归问题 查表通过记忆化避免重复计算从而节省时间如果进一步对问题加以分析和抽象往往还能在空间上进行类似的压缩优化。这一观点在 thinkings/dynamic-programming.md 的记忆化递归章节中有更完整的展开。完整代码实现原文档提供了 JS / C / Python 三种实现中文版另附 Java 版全部可直接运行。各语言版本虽在边界处理与写法上有差异但底层状态转移逻辑完全一致。JavaScript一维 dp 数组版/** * param {number[]} nums * return {number} */ var rob function(nums) { // Tag: DP const dp []; dp[0] 0; dp[1] 0; for (let i 2; i nums.length 2; i) { dp[i] Math.max(dp[i - 2] nums[i - 2], dp[i - 1]); } return dp[nums.length 1]; };该版本完整对应上文的状态转移方程dp[i] Math.max(dp[i - 2] nums[i - 2], dp[i - 1])便于初学者对照验证实际提交时通常使用滚动变量版以省空间。C滚动变量版与 JavaScript 的 dp 数组版略有差异但状态转移方程是一样的。class Solution { public: int rob(vectorint nums) { if (nums.empty()) return 0; auto sz nums.size(); if (sz 1) return nums[0]; auto prev nums[0]; auto cur max(prev, nums[1]); for (auto i 2; i sz; i) { auto tmp cur; cur max(nums[i] prev, cur); prev tmp; } return cur; } };注意此处 C 版本对空数组与单元素数组做了显式边界处理nums.empty()返回 0sz 1返回nums[0]这是与 JS 版错位 dp 数组写法不同的地方但转移方程cur max(nums[i] prev, cur)与 JS 版本质一致。Python滚动变量版class Solution: def rob(self, nums: List[int]) - int: if not nums: return 0 length len(nums) if length 1: return nums[0] else: prev nums[0] cur max(prev, nums[1]) for i in range(2, length): cur, prev max(prev nums[i], cur), cur return curPython 版本利用多重赋值cur, prev max(prev nums[i], cur), cur一步完成状态滚动代码最简洁也最容易看出只用前两个状态这一事实。Java滚动变量版出自中文版题解class Solution { public int rob(int[] nums) { if (nums null || nums.length 0) { return 0; } int length nums.length; if (length 1) { return nums[0]; } int prev nums[0], cur Math.max(nums[0], nums[1]); for (int i 2; i length; i) { int temp cur; cur Math.max(prev nums[i], cur); prev temp; } return cur; } }复杂度分析时间复杂度$O(N)$只需对数组做一次线性扫描N 为房屋数量。空间复杂度一维 dp 数组版$O(N)$滚动变量版$O(1)$仅使用常数个额外变量。关键点解析正确理解抢 / 不抢的二元决策抢当前房子则必须跳过前一个收益为nums[i] dp[i-2]不抢则直接继承dp[i-1]二者取最大值即为转移方程。掌握 dp 数组的错位技巧令dp[0] dp[1] 0使dp[i]对应nums[i-2]从而统一处理边界无需在循环外写额外分支。识别状态依赖的局部性每个dp[i]只依赖前两个状态这是滚动变量优化的依据也是将空间从 O(n) 压到 O(1) 的关键。体会 DP 与斐波那契、爬楼梯的关系本题的转移结构与爬楼梯问题的斐波那契式递推同源理解了本题为什么可以不用 dp 数组也就理解了爬楼梯为什么能用斐波那契数列求解——这正是原文档反复强调的学习价值所在。相关题目与延伸阅读数组升级为树的变体problems/337.house-robber-iii.md打家劫舍 III二叉树结构上的抢 / 不抢决策题目数据结构从线性数组换成了二叉树但对每个节点决策抢与不抢、取价值更大者的思路与本题一脉相承。本仓库将本题收录于 easy 合集collections/easy.md条目0198. 打家劫舍并在文档目录 SUMMARY.md 中归档为0198. 打家劫舍。通用方法论动态规划的完整认知框架记忆化递归、最优子结构、无后效性、状态定义见 thinkings/dynamic-programming.md。总结House Robber 是动态规划入门的最优练习素材之一它用一条街、几间房把状态定义 → 二元决策 → 转移方程 → 滚动优化这条完整链路压缩在几十行代码里。掌握本题你便同时拿到了线性序列 相邻约束类问题如打家劫舍系列、部分股票买卖问题的通用钥匙也为后续理解更复杂的树形 DP、区间 DP 打下坚实基础。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考