1. 动态规划入门：从爬楼梯到打家劫舍
LeetCode上的动态规划问题总是让人又爱又恨——看似简单的题目背后往往隐藏着精妙的解题思路。今天我们就来拆解两个经典题目：70.爬楼梯和198.打家劫舍。这两个问题看似毫不相关，实则都体现了动态规划的核心思想。
我第一次接触爬楼梯问题时，直觉反应是用递归解决。但当输入n=45时，递归解法直接超时，这才意识到问题的复杂性。而打家劫舍问题更是让我栽了跟头——最初尝试用贪心算法，结果发现根本无法覆盖所有情况。经过反复尝试和思考，终于理解了这两个问题背后的动态规划本质。
2. 爬楼梯问题解析
2.1 问题描述与初步思考
爬楼梯问题的描述很简单：假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶。问有多少种不同的方法可以爬到楼顶？
例如：
- n=2时，有2种方法：1+1或直接2
- n=3时，有3种方法：1+1+1、1+2、2+1
看到这个问题，我的第一反应是递归。因为爬到第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)这个解法在小规模输入时工作正常，但当n=45时，运行时间变得不可接受。原因在于递归过程中存在大量重复计算，时间复杂度达到了O(2^n)。
2.3 动态规划解法优化
为了优化性能，我改用动态规划方法，使用一个数组来存储中间结果：
def climbStairs(n): if n == 1: return 1 dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): 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, n+1): first, second = second, first + second return second这样空间复杂度降到了O(1)，这是最优解法。
3. 打家劫舍问题解析
3.1 问题描述与难点
打家劫舍问题描述为：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你的唯一制约因素是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报的情况下，能够偷窃到的最高金额。
例如：
- 输入：[1,2,3,1]
- 输出：4
- 解释：偷窃第1号和第3号房屋(1+3=4)
这个问题比爬楼梯复杂，因为需要考虑更多条件。我最初尝试用贪心算法，每次都选择当前能偷的最大值，但很快就发现这种策略无法保证全局最优。
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 常见错误与调试技巧
在实际编码中，我遇到过几个典型错误：
- 边界条件处理不当：比如n=0或nums为空数组的情况
- 数组越界：特别是在处理dp[i-2]时忘记检查i>=2
- 初始状态设置错误：比如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]*(n+1) dp[0] = 1 for i in range(1, n+1): 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 测试用例设计
为了确保代码正确性，我通常会设计以下几类测试用例：
- 最小输入：n=0或nums=[]
- 小规模输入：手动可验证的简单情况
- 边界情况：如n=1或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特征：
- 计数问题（如爬楼梯的方法数）
- 最值问题（如最大金额、最小成本）
- 存在性判断（如能否分割等和子集）
在实际工程中，动态规划思想也有广泛应用，比如：
- 文本差异比较
- 资源分配优化
- 路径规划问题
我个人的体会是，动态规划的学习曲线虽然陡峭，但一旦掌握了核心思想，很多难题都会迎刃而解。建议从简单题目入手，逐步建立信心，不要一开始就挑战最难的题目。
