动态规划入门：爬楼梯与打家劫舍问题解析

1. 动态规划入门从爬楼梯到打家劫舍LeetCode上的动态规划问题总是让人又爱又恨——看似简单的题目背后往往隐藏着精妙的解题思路。今天我们就来拆解两个经典题目70.爬楼梯和198.打家劫舍。这两个问题看似毫不相关实则都体现了动态规划的核心思想。我第一次接触爬楼梯问题时直觉反应是用递归解决。但当输入n45时递归解法直接超时这才意识到问题的复杂性。而打家劫舍问题更是让我栽了跟头——最初尝试用贪心算法结果发现根本无法覆盖所有情况。经过反复尝试和思考终于理解了这两个问题背后的动态规划本质。2. 爬楼梯问题解析2.1 问题描述与初步思考爬楼梯问题的描述很简单假设你正在爬楼梯需要n阶才能到达楼顶。每次你可以爬1或2个台阶。问有多少种不同的方法可以爬到楼顶例如n2时有2种方法11或直接2n3时有3种方法111、12、21看到这个问题我的第一反应是递归。因为爬到第n阶楼梯要么是从n-1阶跨1步上来要么是从n-2阶跨2步上来。所以递推公式似乎是f(n)f(n-1)f(n-2)。2.2 递归解法及其缺陷基于上述思路我很快写出了递归解法def climbStairs(n): if n 1: return 1 if n 2: return 2 return climbStairs(n-1) climbStairs(n-2)这个解法在小规模输入时工作正常但当n45时运行时间变得不可接受。原因在于递归过程中存在大量重复计算时间复杂度达到了O(2^n)。2.3 动态规划解法优化为了优化性能我改用动态规划方法使用一个数组来存储中间结果def climbStairs(n): if n 1: return 1 dp [0]*(n1) dp[1] 1 dp[2] 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这种方法将时间复杂度降到了O(n)空间复杂度也是O(n)。但进一步观察发现我们其实只需要前两个状态因此可以继续优化空间def climbStairs(n): if n 1: return 1 first, second 1, 2 for _ in range(3, n1): first, second second, first second return second这样空间复杂度降到了O(1)这是最优解法。3. 打家劫舍问题解析3.1 问题描述与难点打家劫舍问题描述为你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你的唯一制约因素是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报的情况下能够偷窃到的最高金额。例如输入[1,2,3,1]输出4解释偷窃第1号和第3号房屋(134)这个问题比爬楼梯复杂因为需要考虑更多条件。我最初尝试用贪心算法每次都选择当前能偷的最大值但很快就发现这种策略无法保证全局最优。3.2 动态规划状态定义经过反复思考我意识到这也是一道动态规划问题。关键在于如何定义状态和状态转移方程。定义dp[i]为偷到第i间房屋时能获得的最大金额。对于第i间房屋有两种选择偷它那么不能偷i-1最大金额是dp[i-2]nums[i]不偷它最大金额保持dp[i-1]因此状态转移方程为 dp[i] max(dp[i-1], dp[i-2]nums[i])3.3 完整解法实现基于这个思路我写出了以下解法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], dp[i-2]nums[i]) return dp[-1]同样地我们可以优化空间复杂度def rob(nums): prev_max curr_max 0 for num in nums: temp curr_max curr_max max(curr_max, prev_max num) prev_max temp return curr_max这种解法时间复杂度O(n)空间复杂度O(1)非常高效。4. 两问题的联系与动态规划思想4.1 问题共性分析爬楼梯和打家劫舍看似不同实则都体现了动态规划的核心特征最优子结构问题的最优解包含子问题的最优解重叠子问题算法会反复计算相同的子问题无后效性当前状态只与前面有限个状态有关4.2 动态规划解题框架通过这两个问题我总结出了动态规划解题的一般步骤定义状态明确dp[i]代表什么含义确定状态转移方程找出dp[i]与前面状态的关系初始化确定初始状态的值考虑边界条件选择计算顺序通常是自底向上空间优化如果可能4.3 常见错误与调试技巧在实际编码中我遇到过几个典型错误边界条件处理不当比如n0或nums为空数组的情况数组越界特别是在处理dp[i-2]时忘记检查i2初始状态设置错误比如dp[1]应该取max(nums[0],nums[1])而非nums[1]调试时我通常会先用小例子手动计算预期结果打印中间状态数组检查是否符合预期特别注意循环的起始和终止条件5. 进阶思考与变种问题5.1 爬楼梯变种原问题中每次只能爬1或2阶如果改为可以爬1、2或3阶呢状态转移方程变为 f(n) f(n-1) f(n-2) f(n-3)如果每次能爬的台阶数是一个数组steps中的任意值则def climbStairsVariation(n, steps): dp [0]*(n1) dp[0] 1 for i in range(1, n1): for step in steps: if i step: dp[i] dp[i-step] return dp[n]5.2 打家劫舍变种LeetCode上还有打家劫舍II房屋围成一圈和打家劫舍III房屋排列成二叉树的变种。以打家劫舍II为例关键思路是将环形问题拆解为两个线性问题不偷第一间房屋不偷最后一间房屋然后取两种情况的最大值def robII(nums): if len(nums) 1: return nums[0] return max(rob(nums[:-1]), rob(nums[1:]))5.3 其他类似问题掌握了这两个问题的解法后我发现很多问题都有相似的模式最小花费爬楼梯每一步有成本求最小总成本最长递增子序列定义dp[i]为以nums[i]结尾的最长子序列长度最大子数组和Kadane算法的动态规划版本6. 实战经验与性能优化6.1 测试用例设计为了确保代码正确性我通常会设计以下几类测试用例最小输入n0或nums[]小规模输入手动可验证的简单情况边界情况如n1或nums长度刚好为2大规模输入测试性能6.2 时间与空间复杂度分析对于动态规划问题通常时间复杂度O(n)因为需要遍历所有状态空间复杂度基础版本O(n)优化后O(1)当遇到更复杂的状态定义时如二维dp复杂度会相应增加。6.3 实际编码技巧在实现过程中我总结了一些实用技巧使用注释明确每个状态的定义先写出基础版本确保正确后再优化空间对于Python可以用元组同时更新多个变量避免临时变量在循环开始时处理边界条件使主逻辑更清晰7. 学习资源与练习建议7.1 推荐学习路径对于想系统学习动态规划的同学我建议的学习顺序是斐波那契数列 → 爬楼梯 → 打家劫舍背包问题系列01背包、完全背包字符串相关DP最长公共子序列、编辑距离更复杂的二维DP问题7.2 经典题目清单以下是我认为必做的动态规划题目爬楼梯打家劫舍最大子数组和零钱兑换最长递增子序列最长公共子序列7.3 刷题策略建议根据我的经验有效的刷题策略是先独立思考至少尝试30分钟如果卡住看提示而非完整解答理解解法后自己重新实现24小时后再次尝试同一题目总结相似题目的解题模式8. 从理论到实践的思考动态规划之所以难是因为它需要我们将问题分解并找到合适的状态定义。经过大量练习后我开始能够识别问题的DP特征计数问题如爬楼梯的方法数最值问题如最大金额、最小成本存在性判断如能否分割等和子集在实际工程中动态规划思想也有广泛应用比如文本差异比较资源分配优化路径规划问题我个人的体会是动态规划的学习曲线虽然陡峭但一旦掌握了核心思想很多难题都会迎刃而解。建议从简单题目入手逐步建立信心不要一开始就挑战最难的题目。