动态规划入门：LeetCode爬楼梯问题解法全解析

1. 问题描述与初步理解

LeetCode 70题"Climbing Stairs"是算法学习中的经典入门题目。题目描述很简单：假设你正在爬楼梯，每次可以跨1阶或2阶，问到达第n阶有多少种不同的方法。这个看似简单的问题，实际上蕴含着动态规划的核心思想。

我第一次遇到这个问题时，直觉反应是用递归解决。毕竟，要到达第n阶，要么从n-1阶跨1步上来，要么从n-2阶跨2步上来。所以f(n)=f(n-1)+f(n-2)。这个思路看起来合理，但实际编码时会发现性能问题——普通的递归解法会有大量重复计算，时间复杂度是指数级的O(2^n)。

2. 递归解法与优化

2.1 基础递归实现

我们先来看最直观的递归解法代码：

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

这个解法虽然逻辑正确，但当n增大时效率极低。比如计算climbStairs(5)时，会重复计算climbStairs(3)和climbStairs(2)多次。这种重复计算在n较大时会导致严重的性能问题。

2.2 记忆化递归优化

为了优化这个递归解法，我们可以引入记忆化技术，将已经计算过的结果存储起来：

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

这种记忆化递归将时间复杂度降低到了O(n)，因为每个子问题只需要计算一次。空间复杂度也是O(n)，因为需要存储n个中间结果。

3. 动态规划解法

3.1 自底向上的动态规划

更高效的解法是使用动态规划，采用自底向上的方式：

def climbStairs(n: int) -> int: 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)的空间复杂度。但相比递归，迭代的方式通常有更好的实际运行性能。

3.2 空间优化的动态规划

观察上面的动态规划解法，我们发现实际上只需要保存前两个状态的值，因此可以进一步优化空间：

def climbStairs(n: int) -> int: if n == 1: return 1 first, second = 1, 2 for _ in range(3, n + 1): first, second = second, first + second return second

这个优化版本将空间复杂度降低到了O(1)，只使用了常数级别的额外空间，是这个问题的最优解法之一。

4. 数学解法与斐波那契数列

4.1 问题与斐波那契数列的关系

仔细观察这个问题，我们会发现它实际上就是斐波那契数列的变种。斐波那契数列定义为F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)。而我们的爬楼梯问题是f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2)。也就是说，f(n) = F(n+1)。

4.2 通项公式解法

斐波那契数列有通项公式（比奈公式）： F(n) = (φ^n - ψ^n)/√5，其中φ=(1+√5)/2≈1.618，ψ=(1-√5)/2≈-0.618

因此我们可以直接计算：

def climbStairs(n: int) -> int: sqrt5 = 5 ** 0.5 phi = (1 + sqrt5) / 2 return int((phi ** (n + 1) - (-phi) ** (-n - 1)) / sqrt5)

这个解法的时间复杂度是O(1)（假设幂运算是常数时间），但由于浮点数精度问题，当n较大时可能会有精度误差。

4.3 矩阵快速幂解法

更精确的O(log n)解法是使用矩阵快速幂：

def climbStairs(n: int) -> int: def matrix_pow(mat, power): result = [[1,0],[0,1]] # 单位矩阵 while power > 0: if power % 2 == 1: result = matrix_mult(result, mat) mat = matrix_mult(mat, mat) power //= 2 return result def matrix_mult(a, b): return [ [a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]], [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]] ] if n == 1: return 1 mat = [[1,1],[1,0]] result = matrix_pow(mat, n - 1) return result[0][0] + result[0][1]

这个解法在理论上有更好的时间复杂度，但在实际编程竞赛中，对于n不是特别大的情况，简单的动态规划通常已经足够。

5. 不同解法的比较与选择

5.1 时间复杂度对比

5.2 实际编码建议

在实际编程中，对于LeetCode这类平台，n通常不会太大（一般n≤45），因此空间优化的动态规划解法是最佳选择：

1. 代码简洁易懂
2. 时间和空间效率都很好
3. 没有精度问题
4. 适用于面试场景

只有在极端情况下（如n非常大，比如n>10^6），才需要考虑矩阵快速幂等更复杂的解法。

6. 变种问题与扩展思考

6.1 一次可以爬1、2或3阶

如果题目改为每次可以爬1、2或3阶楼梯，递推关系变为f(n)=f(n-1)+f(n-2)+f(n-3)。这时动态规划的解法和之前类似：

def climbStairs(n: int) -> int: if n == 1: return 1 if n == 2: return 2 if n == 3: return 4 a, b, c = 1, 2, 4 for _ in range(4, n + 1): a, b, c = b, c, a + b + c return c

6.2 有障碍物的爬楼梯问题

这是LeetCode 70题的变种，在楼梯的某些台阶上设置了障碍物。这时我们需要修改动态规划的状态转移方程：

def climbStairsWithObstacles(obstacles: List[int]) -> int: n = len(obstacles) if n == 0: return 0 dp = [0] * (n + 1) dp[0] = 1 for i in range(1, n + 1): if obstacles[i-1] == 1: dp[i] = 0 else: dp[i] = dp[i-1] + (dp[i-2] if i >= 2 else 0) return dp[n]

6.3 最小花费爬楼梯

另一个常见变种是LeetCode 746题"Min Cost Climbing Stairs"，每个台阶有一个cost，求到达顶部的最小花费：

def minCostClimbingStairs(cost: List[int]) -> int: n = len(cost) dp = [0] * (n + 1) for i in range(2, n + 1): dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) return dp[n]

7. 面试技巧与常见错误

7.1 面试中如何回答这个问题

在面试中遇到这个问题时，建议按照以下步骤回答：

1. 先明确问题，确认理解正确
2. 从最直观的递归解法开始
3. 指出递归解法的问题（重复计算）
4. 提出记忆化递归优化
5. 进一步优化为动态规划
6. 最后给出空间优化的动态规划解法
7. 如果时间允许，可以讨论斐波那契数列的关系

7.2 常见错误与注意事项

1. 边界条件处理：n=1和n=2的情况需要单独处理
2. 数组越界：在动态规划解法中，确保dp数组大小正确
3. 初始条件设置：确保dp[1]和dp[2]正确初始化
4. 变量命名：使用有意义的变量名，如prev, curr比a, b更易读
5. 空间优化：在面试中，可以先给出基础DP解法，再优化空间

7.3 测试用例建议

验证代码时，建议测试以下情况：

• n=1（最小输入）
• n=2
• n=3（验证递推关系）
• n=10（中等大小）
• n=45（LeetCode上的最大测试用例）

8. 实际应用与延伸学习

8.1 动态规划的应用场景

爬楼梯问题是理解动态规划的绝佳起点。类似的动态规划问题包括：

• 斐波那契数列
• 硬币找零问题
• 最长递增子序列
• 背包问题
• 编辑距离

8.2 推荐练习题

为了巩固动态规划的理解，建议尝试以下LeetCode题目：

• 746. Min Cost Climbing Stairs
• 198. House Robber
• 62. Unique Paths
• 64. Minimum Path Sum
• 53. Maximum Subarray

8.3 学习资源推荐

1. 《算法导论》动态规划章节
2. LeetCode动态规划专题
3. 《剑指Offer》中的动态规划问题
4. 极客时间的算法面试课程
5. 灵茶山艾府的动态规划题解

9. 个人经验与心得

在实际刷题过程中，我发现动态规划问题有几个关键点：

1. 定义清晰的状态：明确dp[i]表示什么
2. 找出正确的状态转移方程
3. 确定初始条件
4. 考虑空间优化可能性

对于爬楼梯问题，我建议初学者：

1. 先写出递归关系
2. 画出递归树理解重复计算
3. 手动计算小例子验证思路
4. 逐步优化到最佳解法

记住，动态规划的核心思想是"记住已经解决的子问题的答案"，避免重复计算。掌握了这个思想，就能解决更复杂的动态规划问题。