动态规划解爬楼梯问题：从斐波那契到矩阵快速幂

1. 爬楼梯问题的数学本质

爬楼梯问题是一个经典的动态规划入门题目，表面上看似简单，实则蕴含着深刻的数学原理。假设你正在爬一个有n个台阶的楼梯，每次可以跨1个或2个台阶，问有多少种不同的方法可以爬到楼顶。

这个问题实际上等价于斐波那契数列问题。让我们从数学角度分析：当n=1时，只有1种方法（一步登顶）；n=2时，有2种方法（1+1或直接跨2步）；n=3时，有3种方法（1+1+1，1+2，2+1）。可以看到，这正是斐波那契数列的递推关系：f(n) = f(n-1) + f(n-2)。

关键理解：每个台阶的到达方式，要么是从前一个台阶跨1步上来，要么是从前两个台阶跨2步上来。这就是递推关系的核心逻辑。

2. 递归解法及其局限性

最直观的解法是使用递归：

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

但这种朴素递归存在严重效率问题。以计算climbStairs(5)为例：

• 需要计算climbStairs(4)和climbStairs(3)
• clibStairs(4)又需要计算climbStairs(3)和climbStairs(2)
• 可以看到climbStairs(3)被重复计算了

时间复杂度达到O(2^n)，当n较大时完全不可行。这就是递归解法在实际应用中最大的痛点。

3. 动态规划的标准解法

动态规划是解决这类问题的标准方法。我们可以使用两种实现方式：

3.1 自底向上的迭代法

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]

这种方法：

1. 创建了一个dp数组存储中间结果
2. 初始化基础情况（n=1和n=2）
3. 通过循环逐步构建更大问题的解
4. 时间复杂度O(n)，空间复杂度O(n)

3.2 空间优化版本

观察到每个状态只依赖前两个状态，可以进一步优化空间：

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)，只使用常数空间，是面试中最推荐的写法。

4. 矩阵快速幂解法

对于追求极致效率的场景，我们可以使用矩阵快速幂将时间复杂度降到O(log n)：

def climbStairs(n): 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] * 2 + result[0][1] * 1

这种方法基于斐波那契数列的矩阵表示形式，通过快速幂算法大幅提升计算效率，特别适合n非常大的情况（比如n>10^6）。

5. 通用化问题扩展

实际问题中，楼梯问题的变种非常多，常见的有：

5.1 可变步长版本

如果每次可以跨1、2或3个台阶，解法只需修改递推关系：

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

5.2 带障碍物版本

LeetCode 63题就是在网格中加入障碍物：

def uniquePathsWithObstacles(grid): m, n = len(grid), len(grid[0]) dp = [[0]*n for _ in range(m)] dp[0][0] = 1 if grid[0][0] == 0 else 0 for i in range(1, m): dp[i][0] = dp[i-1][0] if grid[i][0] == 0 else 0 for j in range(1, n): dp[0][j] = dp[0][j-1] if grid[0][j] == 0 else 0 for i in range(1, m): for j in range(1, n): if grid[i][j] == 1: dp[i][j] = 0 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]

5.3 最小代价爬楼梯

LeetCode 746题要求计算最小花费：

def minCostClimbingStairs(cost): 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]

6. 实际工程中的应用场景

爬楼梯问题看似简单，但其解法模式在工程中有广泛应用：

1. 支付系统：计算组合支付方式（如用不同面额硬币支付一定金额）
2. 文本处理：计算字符串解码方式的数量（如A=1，B=2，...，Z=26）
3. 游戏设计：角色移动路径计算
4. 金融分析：计算投资组合的可能配置方式

以字符串解码为例的代码实现：

def numDecodings(s): if not s: return 0 n = len(s) dp = [0]*(n+1) dp[0] = 1 dp[1] = 0 if s[0] == '0' else 1 for i in range(2, n+1): if s[i-1] != '0': dp[i] += dp[i-1] two_digit = int(s[i-2:i]) if 10 <= two_digit <= 26: dp[i] += dp[i-2] return dp[n]

7. 算法选择与性能对比

不同解法在不同场景下的表现：

在实际编程面试中，推荐使用空间优化的动态规划解法，它兼具了代码简洁性和高效性。对于特别大的n（如n>10^6），矩阵快速幂是唯一可行的方案。

8. 常见错误与调试技巧

新手在解决这类问题时容易犯的错误：

1. 边界条件处理不当：忘记处理n=0或n=1的特殊情况
2. 索引越界：dp数组大小设置错误
3. 递推关系错误：混淆f(n-1)和f(n-2)的顺序
4. 整数溢出：当n很大时结果可能超出整数范围

调试建议：

• 先用小例子手工计算验证
• 打印dp数组中间值检查是否正确
• 添加详细的注释说明每个步骤的意图

例如，这是一个带有调试输出的实现：

def climbStairs(n): if n == 1: return 1 dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 print(f"初始化：dp[1]={dp[1]}, dp[2]={dp[2]}") for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] print(f"计算dp[{i}]: {dp[i-1]} + {dp[i-2]} = {dp[i]}") return dp[n]

9. 数学通项公式解法

斐波那契数列其实有通项公式（Binet公式）：

f(n) = (φ^n - ψ^n)/√5，其中φ=(1+√5)/2≈1.618，ψ=(1-√5)/2≈-0.618

Python实现：

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

注意：

1. 由于浮点数精度问题，当n较大时结果可能不准确
2. 在实际编程比赛中，通常会要求对结果取模来避免大数问题

10. 不同语言实现对比

最后我们看看在不同编程语言中的实现差异：

Java实现：

public int climbStairs(int n) { if (n == 1) return 1; int[] dp = new int[n+1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }

C++实现：

int climbStairs(int n) { if (n == 1) return 1; vector<int> dp(n+1); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; ++i) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }

JavaScript实现：

function climbStairs(n) { if (n === 1) return 1; let dp = new Array(n+1); dp[1] = 1; dp[2] = 2; for (let i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }

Go实现：

func climbStairs(n int) int { if n == 1 { return 1 } dp := make([]int, n+1) dp[1] = 1 dp[2] = 2 for i := 3; i <= n; i++ { dp[i] = dp[i-1] + dp[i-2] } return dp[n] }

从这些实现可以看出，虽然语法不同，但核心算法逻辑是完全一致的。这也体现了动态规划作为一种算法范式的通用性。