1. 爬楼梯问题与动态规划的天然契合

第一次看到LeetCode 70题"爬楼梯"时，很多人会下意识地用递归暴力破解——这确实能得到正确答案，但效率低得可怕。直到某次面试中，当面试官要求我计算爬100级台阶的方法数时，我才真正理解动态规划（DP）在这个问题中的精妙之处。

这个问题描述很简单：假设你正在爬楼梯，每次可以跨1或2个台阶。问到达第n级台阶有多少种不同的方法？当n=2时，有(1+1)和(2)两种方法；n=3时有(1+1+1, 1+2, 2+1)三种。看起来像是组合数学问题，但DP给出了更优雅的解法。

为什么DP特别适合这类问题？因为爬楼梯满足DP的两个核心性质：

• 最优子结构：到达第n阶的方法数，取决于n-1和n-2阶的方法数
• 重叠子问题：计算f(n)需要重复计算f(n-1)、f(n-2)等

关键理解：把"有多少种走法"的问题转化为"最后一步是从哪来"的决策问题。这是DP思维的关键转折点。

2. 从暴力递归到记忆化搜索的演进路径

2.1 递归解法及其缺陷

最直观的解法是递归：

def climbStairs(n): if n == 1: return 1 if n == 2: return 2 return climbStairs(n-1) + climbStairs(n-2)

这个解法虽然正确，但时间复杂度是O(2^n)——因为每次调用都会分裂成两个子调用。计算climbStairs(40)可能需要几分钟！

2.2 记忆化搜索优化

通过添加缓存来存储已计算结果：

memo = {} def climbStairs(n): if n in memo: return memo[n] if n == 1: return 1 if n == 2: return 2 memo[n] = climbStairs(n-1) + climbStairs(n-2) return memo[n]

时间复杂度立即降为O(n)，因为每个n值只计算一次。这是DP的雏形，但递归调用栈仍有O(n)空间开销。

2.3 空间复杂度的隐藏陷阱

即使使用记忆化，当n=10000时递归解法仍会爆栈。这是很多人在面试中容易忽略的点：

递归解法在理论上是正确的，但在工程实践中可能不可行。这是为什么要掌握迭代DP写法的重要原因。

3. 标准动态规划解法的实现细节

3.1 状态定义与转移方程

DP的核心是明确：

• dp[i]的定义：到达第i阶的方法数
• 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
• 边界条件：dp[1]=1, dp[2]=2

3.2 迭代实现

def climbStairs(n): if n <= 2: return n dp = [0]*(n+1) dp[1], dp[2] = 1, 2 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

时间复杂度O(n)，空间复杂度O(n)。这是最标准的DP写法，清晰展现了DP的核心要素。

3.3 空间优化技巧

观察发现dp[i]只依赖前两个状态，因此可以优化为：

def climbStairs(n): if n <= 2: return n a, b = 1, 2 for _ in range(3, n+1): a, b = b, a+b return b

空间复杂度降为O(1)。这是面试官最希望看到的写法。

4. 动态规划的本质与思维训练

4.1 为什么这不是斐波那契数列

虽然数学形式相同，但两者的物理意义完全不同：

• 斐波那契：f(0)=0, f(1)=1
• 爬楼梯：dp[0]无意义，dp[1]=1, dp[2]=2

算法题重要的是问题建模能力，而不是死记硬背公式。这是很多刷题新手容易犯的错误。

4.2 DP与分治法的区别

两者都涉及子问题分解，但关键差异在于：

• 分治法：子问题互不重叠（如归并排序）
• DP：子问题大量重叠，需要记忆化

4.3 如何识别DP适用问题

当问题具有以下特征时考虑DP：

1. 求最大/最小值或方案总数
2. 问题可以分解为子问题
3. 子问题之间存在重叠
4. 具有最优子结构性质

5. 变种问题与实际应用场景

5.1 步长变化的扩展

如果每次可以走1、2或3步，解法只需修改转移方程：

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

5.2 带障碍的爬楼梯（LeetCode 91）

某些台阶不可踏足时，只需在转移时判断：

if obstacle[i] == 1: dp[i] = 0 else: dp[i] = dp[i-1] + dp[i-2]

5.3 最小花费爬楼梯（LeetCode 746）

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

5.4 实际工程应用

• 机器人路径规划
• 游戏角色移动逻辑
• 金融中的期权定价模型
• 编译器中的指令调度

6. 常见错误与调试技巧

6.1 边界条件处理

新手常犯的错误：

• 忘记处理n=0的情况
• dp数组大小误设为n而非n+1
• 初始化时漏掉dp[2]的情况

6.2 空间优化时的陷阱

当使用滚动变量优化空间时：

# 错误写法： a = b b = a + b # 此时a已经是新的b值 # 正确写法： a, b = b, a + b

6.3 大数测试用例

当n很大时（如1e5），需要注意：

• Python默认递归深度限制（通常1000）
• 整数溢出问题（Python无此问题，但其他语言需考虑）
• 结果取模要求（如题目要求结果mod 1e9+7）

7. 从爬楼梯到DP思维的进阶之路

理解爬楼梯问题后，可以尝试这些经典DP问题：

1. 最长递增子序列（LIS）
2. 背包问题系列
3. 编辑距离
4. 股票买卖问题
5. 打家劫舍系列

每道题都体现了不同的状态定义技巧：

• 一维状态（爬楼梯）
• 二维状态（编辑距离）
• 带维度状态（背包问题）
• 状态机（股票问题）

我在准备算法面试时，会专门记录每种状态定义的模式，这比死记硬背代码有效得多。比如爬楼梯这类"线性DP"问题，状态定义通常是"以i结尾的某种性质"，而转移方程往往只涉及前几个状态。