★ FEATURED ARTICLE 1. 问题背景与核心约束这道题目来自力扣第83题打家劫舍是动态规划领域的经典入门问题。题目设定你是一个专业的小偷需要在一排房屋中选择偷窃目标但必须遵守一个核心规则不能连续偷窃相邻的两间房屋否则会触发报警系统。问题的数学描述是给定一个非负整数数组nums其中nums[i]表示第i间房屋中的现金金额需要找出一个子序列使得子序列中相邻元素在原始数组中不相邻且该子序列的和最大。注意虽然题目以小偷为背景但实际考察的是对动态规划思想的理解和应用能力。这类问题在现实中也有广泛应用比如在资源调度、投资决策等场景中。2. 动态规划解法详解2.1 状态定义与转移方程动态规划的核心在于找到合适的状态定义和状态转移方程。对于这个问题我们可以定义dp[i]表示偷窃到第i间房屋时能获得的最大金额考虑第i间房屋时我们有两种选择偷窃第i间房屋那么不能偷窃第i-1间最大金额为dp[i-2] nums[i]不偷窃第i间房屋最大金额保持为dp[i-1]因此状态转移方程为 dp[i] max(dp[i-1], dp[i-2] nums[i])2.2 边界条件处理初始状态需要特别处理dp[0] nums[0] 只有一间房屋时dp[1] max(nums[0], nums[1]) 两间房屋时取较大值2.3 代码实现Pythondef 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], dp[i-2] nums[i]) return dp[-1]2.4 空间复杂度优化观察状态转移方程可以发现dp[i]只依赖于dp[i-1]和dp[i-2]因此可以用两个变量代替整个dp数组def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] prev2 nums[0] prev1 max(nums[0], nums[1]) for i in range(2, len(nums)): current max(prev1, prev2 nums[i]) prev2, prev1 prev1, current return prev1这样空间复杂度从O(n)降到了O(1)。3. 算法正确性证明3.1 数学归纳法验证我们可以用数学归纳法证明这个动态规划解法的正确性基例当n1时显然只能偷这一间dp[0]nums[0]正确当n2时取两者较大值dp[1]max(nums[0],nums[1])正确归纳假设 假设对于所有k idp[k]都是正确的归纳步骤 对于dp[i]根据定义只有两种可能不偷第i间则最大金额为dp[i-1]偷第i间则最大金额为dp[i-2]nums[i] 取两者较大值即为最优解因此dp[i]也正确3.2 反证法思考假设存在一个更优的方案那么它要么在某个位置违反了不连续偷窃的规则要么实际金额不大于我们的dp解。通过反证可以确认我们的解法确实能得到全局最优解。4. 复杂度分析与优化4.1 时间复杂度无论是原始解法还是优化后的解法都只需要一次遍历数组因此时间复杂度为O(n)其中n是数组长度。4.2 空间复杂度原始解法O(n)需要存储整个dp数组优化解法O(1)只使用常数个额外空间4.3 进一步优化思路如果问题规模非常大比如n10^6可以考虑并行计算或分段处理。但在力扣的题目范围内O(n)的解法已经足够高效。5. 常见错误与调试技巧5.1 边界条件处理不当常见错误忘记处理空数组的情况当数组长度为1时直接使用dp[1]导致越界调试技巧首先手动验证小规模测试用例n0,1,2添加打印语句检查dp数组的填充过程5.2 状态转移方程错误常见错误错误地写成dp[i] max(dp[i-1], dp[i-1] nums[i])忽略了不连续偷窃的约束条件调试方法用示例[2,1,1,2]手动计算dp数组正确结果应该是4偷第1和第4间错误解法会得到3偷第1和第3间5.3 空间优化时的变量更新顺序常见错误 prev2, prev1 prev1, current 如果写成 prev1 current prev2 prev1 会导致错误解决方法使用Python的多重赋值或临时变量仔细检查变量更新顺序6. 变种问题与扩展思考6.1 环形房屋排列如果房屋排成一个环形即第一间和最后一间相邻该如何解决解法思路分解为两个子问题不偷第一间求nums[1..n-1]的最大值不偷最后一间求nums[0..n-2]的最大值取两者较大值6.2 二叉树房屋排列如果房屋排列成二叉树结构且不能同时偷直接相连的两个房屋如何解决解法思路对每个节点记录两个状态偷当前节点时的最大值不偷当前节点时的最大值后序遍历二叉树递归计算6.3 连续偷窃不超过k间如果不允许连续偷窃超过k间房屋如何扩展解法解法思路状态定义需要记录最后连续偷窃的房屋数dp[i][j]表示偷到第i间且已连续偷窃j间的最大值状态转移会更复杂需要考虑多种情况7. 实际应用场景虽然题目设定是小偷问题但类似的思想可以应用于资源调度选择不相邻的任务以获得最大收益投资决策不能连续投资高风险项目时的最优组合时间安排选择不相邻的时间段安排活动提示理解这类问题的关键在于识别不能连续选择这一约束条件以及如何通过状态定义来满足这一约束。8. 个人解题心得在解决这类动态规划问题时我发现以下步骤很有帮助先用小规模例子手动计算理解问题本质明确状态定义确保覆盖所有可能性仔细推导状态转移方程考虑所有约束条件特别注意边界条件的处理先写出基础解法再考虑空间优化对于这道题最容易出错的地方是初始条件的处理。我建议在写代码前先手动计算几个小例子比如[] → 0[5] → 5[1,2] → 2[2,1,1,2] → 4这样可以验证算法的正确性。另外空间优化的技巧虽然重要但建议先写出清晰的原始解法确保正确后再进行优化。
阅读完成 · 觉得有帮助？
