1. 问题背景与核心需求打家劫舍是力扣LeetCode平台上经典的动态规划问题编号198题原输入可能有误。这个问题模拟了一个小偷在一条街道上偷窃房屋的场景每间房屋都有一定金额的财物相邻房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚被闯入系统会自动报警。核心需求是给定一个代表每个房屋存放金额的非负整数数组计算小偷在不触动警报装置的情况下一夜之内能够偷窃到的最高金额。例如对于输入数组 [1,2,3,1]最优解是偷窃第1和第3间房屋134。这个问题看似简单但它完美展现了动态规划的核心思想——将复杂问题分解为重叠子问题并通过记忆化存储避免重复计算。这也是为什么它会被选入力扣热题100这个经典题库中。2. 动态规划解法详解2.1 状态定义与转移方程对于第i间房屋小偷有两个选择偷窃它那么不能偷窃i-1最大金额为nums[i] dp[i-2]不偷它最大金额保持为dp[i-1]因此状态转移方程为 dp[i] max(dp[i-1], nums[i] dp[i-2])其中dp[i]表示前i间房屋能偷窃到的最大金额。这个方程就是典型的动态规划递推关系。2.2 基础实现代码def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] dp [0] * len(nums) dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] max(dp[i-1], nums[i] dp[i-2]) return dp[-1]这个实现时间复杂度O(n)空间复杂度O(n)。对于输入[1,2,3,1]初始化dp [1,2,0,0]i2: dp[2] max(2, 31) 4i3: dp[3] max(4, 12) 4最终返回42.3 空间优化版本观察到dp[i]只依赖于前两个状态可以优化空间复杂度到O(1)def rob(nums): prev, curr 0, 0 for num in nums: prev, curr curr, max(curr, prev num) return curr这里用prev代替dp[i-2]curr代替dp[i-1]通过变量滚动实现空间优化。3. 边界条件与特殊测试用例3.1 必须处理的边界情况空数组应该返回0单元素数组直接返回该元素值两元素数组返回较大的那个值这些边界在面试中经常被考察忽略会导致代码无法通过所有测试用例。3.2 典型测试用例示例测试用例1: [1,2,3,1] → 4 测试用例2: [2,7,9,3,1] → 12 (291) 测试用例3: [2,1,1,2] → 4 (22) 测试用例4: [] → 0 测试用例5: [5] → 5特别注意测试用例3最优解不是连续间隔偷窃而是跳着选择更大的数字组合。4. 算法正确性证明4.1 数学归纳法证明基础情况i0: dp[0]nums[0] 正确i1: dp[1]max(nums[0],nums[1]) 正确归纳假设 假设对于所有k idp[k]都是前k间房屋的最优解归纳步骤 对于dp[i]根据状态转移方程如果选择偷i则金额为nums[i]dp[i-2]如果不偷i则金额为dp[i-1] 取两者最大值必然得到前i间房屋的最优解4.2 反证法说明假设存在一个更优解不遵循这个转移方程那么要么在某个位置应该偷但没偷导致总金额不是最大要么在某个位置不该偷但偷了触发警报 因此我们的解法确实能得到全局最优解。5. 相关问题变种5.1 环形房屋排列力扣213题当房屋排成环形时第一间和最后一间相邻。解决方法分别计算去掉首元素和去掉尾元素的两个子数组的解取两者最大值def rob(nums): if len(nums) 1: return nums[0] return max(rob_linear(nums[1:]), rob_linear(nums[:-1]))5.2 二叉树房屋排列力扣337题当房屋构成二叉树结构时不能同时偷直接相连的父子节点。需要后序遍历def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) rob node.val left[1] right[1] not_rob max(left) max(right) return (rob, not_rob) return max(dfs(root))返回一个元组(偷当前节点的最大值不偷当前节点的最大值)6. 动态规划问题解题框架通过这个问题我们可以总结解决动态规划问题的通用步骤定义子问题明确dp[i]代表什么写出转移方程如何用更小的子问题解来构建当前解确定初始条件最小子问题的解是什么计算顺序通常从简单子问题逐步计算到复杂问题空间优化看是否可以压缩状态存储提示动态规划问题的难点往往在于状态定义。好的状态定义应该满足完备性能够覆盖所有可能情况无后效性当前状态只与之前状态有关与之后无关7. 常见错误与调试技巧7.1 典型错误实现错误示例1贪心算法取间隔元素def rob(nums): sum1 sum(nums[::2]) # 奇数位 sum2 sum(nums[1::2]) # 偶数位 return max(sum1, sum2)这在[2,1,1,2]会失败正确解是4(22)但贪心只能得到3错误示例2忽略边界条件def rob(nums): dp [0] * len(nums) dp[0] nums[0] dp[1] nums[1] # 错误应该是max(nums[0],nums[1]) ...7.2 调试方法打印dp表格观察每个步骤的状态值手动计算小测试用例验证边界条件对比暴力解法对于小规模数据可以用递归暴力解法验证注意在面试中即使暂时无法优化空间复杂度也应该先给出基础DP解法再考虑优化8. 复杂度分析与优化8.1 时间复杂度两种实现都是O(n)因为需要遍历整个数组一次。8.2 空间复杂度基础版本O(n)的dp数组优化版本O(1)只用了两个变量在实际应用中如果不需要回溯具体偷窃路径空间优化版本总是更优。8.3 进一步优化思路如果问题要求输出具体偷窃了哪些房屋可以用额外数组记录选择路径或者反向追踪dp数组决策9. 实际应用场景虽然问题设定是小偷场景但类似思想可用于投资选择不能连续选择有冲突的项目日程安排选择不冲突的会议使参与价值最大资源分配在约束条件下最大化利用效率这类问题的共同特点是需要做一系列决策每个决策会影响后续可选范围目标是整体最优而非局部最优10. 扩展学习建议动态规划经典问题背包问题最长公共子序列股票买卖问题推荐练习题力扣70题爬楼梯力扣120题三角形最小路径和力扣300题最长递增子序列学习资源《算法导论》动态规划章节力扣动态规划专题卡片经典MIT动态规划公开课掌握这类问题的关键在于多练习培养将实际问题抽象为状态转移方程的能力。建议从简单问题开始逐步增加难度同时注意总结各类问题的共性模式。