LeetCode爬楼梯问题解法与性能优化全解析

2025年12月17日 互联网

LeetCode爬楼梯问题解法与性能优化全解析

一、问题定义与基础分析

LeetCode爬楼梯问题（Climbing Stairs）是经典的动态规划入门题，题目描述为：假设每次可以爬1阶或2阶楼梯，给定楼梯总阶数n，求有多少种不同的爬法。该问题本质是斐波那契数列的变种，其数学表达式为：f(n) = f(n-1) + f(n-2)，其中f(1)=1，f(2)=2。

1.1 递归解法：直观但低效

最直观的解法是递归，直接按照数学定义实现：

  1. def climbStairs_recursive(n):
  2.     if n == 1: return 1
  3.     if n == 2: return 2
  4.     return climbStairs_recursive(n-1) + climbStairs_recursive(n-2)

问题：时间复杂度O(2^n)，存在大量重复计算。例如计算f(5)时，f(3)会被计算两次，f(2)会被计算三次。

1.2 递归优化：记忆化搜索

通过缓存中间结果避免重复计算，将时间复杂度降至O(n)，空间复杂度O(n)：

  1. def climbStairs_memo(n, memo={1:1, 2:2}):
  2.     if n not in memo:
  3.         memo[n] = climbStairs_memo(n-1, memo) + climbStairs_memo(n-2, memo)
  4.     return memo[n]

关键点：使用字典存储已计算结果，自顶向下递归。

二、动态规划：自底向上的高效解法

动态规划通过填充表格逐步求解，避免递归的栈开销，是解决此类问题的标准方法。

2.1 基础动态规划实现

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

优化点：

  • 空间复杂度O(n)：存储所有中间结果
  • 时间复杂度O(n)：单次遍历填充表格

2.2 空间优化：滚动数组

观察到每次计算仅依赖前两个状态，可将空间复杂度降至O(1)：

  1. def climbStairs_optimized(n):
  2.     if n == 1: return 1
  3.     a, b = 1, 2
  4.     for _ in range(3, n+1):
  5.         a, b = b, a + b
  6.     return b

实现逻辑：

  • 使用两个变量a和b分别表示f(n-2)和f(n-1)
  • 每次迭代更新a = b，b = a + b（注意更新顺序）

三、进阶解法：矩阵快速幂与通项公式

3.1 矩阵快速幂

将递推关系转化为矩阵乘法，利用快速幂算法将时间复杂度降至O(log n)：

  1. def climbStairs_matrix(n):
  2.     def matrix_pow(mat, power):
  3.         result = [[1, 0], [0, 1]]  # 单位矩阵
  4.         while power > 0:
  5.             if power % 2 == 1:
  6.                 result = matrix_multiply(result, mat)
  7.             mat = matrix_multiply(mat, mat)
  8.             power //= 2
  9.         return result
  11.     def matrix_multiply(a, b):
  12.         return [
  13.             [a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
  14.             [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]]
  15.         ]
  17.     if n == 1: return 1
  18.     mat = [[1, 1], [1, 0]]
  19.     result = matrix_pow(mat, n-1)
  20.     return result[0][0] * 2  # 初始条件f(2)=2的调整

适用场景：当n极大时（如n>1e6），矩阵快速幂显著优于动态规划。

3.2 通项公式

利用斐波那契数列的闭式解（Binet公式），但需处理浮点数精度问题：

  1. import math
  2. def climbStairs_formula(n):
  3.     sqrt5 = math.sqrt(5)
  4.     phi = (1 + sqrt5) / 2
  5.     psi = (1 - sqrt5) / 2
  6.     return int((phi**n - psi**n) / sqrt5)

注意事项：

  • 仅适用于理论分析，实际编程中因浮点误差可能导致结果错误
  • 不推荐在工程中直接使用

四、性能对比与选型建议

方法 时间复杂度 空间复杂度 适用场景
递归 O(2^n) O(n) 教学演示，不推荐实际使用
记忆化搜索 O(n) O(n) 小规模n，需快速实现时
动态规划 O(n) O(n) 中等规模n，代码清晰优先
滚动数组优化 O(n) O(1) 通用最优解，推荐首选
矩阵快速幂 O(log n) O(1) 极大n（如n>1e6）时

工程实践建议：

  1. 默认选择滚动数组优化，兼顾时间与空间效率
  2. 当n>1e5时，考虑矩阵快速幂
  3. 避免纯递归实现，除非用于教学目的

五、扩展思考：动态规划问题设计模式

爬楼梯问题揭示了动态规划问题的通用解法：

  1. 定义状态：明确f(n)的含义（如本题中f(n)表示爬n阶楼梯的方法数）
  2. 状态转移方程：找出f(n)与f(i)（i<n）的关系（f(n)=f(n-1)+f(n-2)）
  3. 初始条件：确定f(0)、f(1)等基例（本题中f(1)=1，f(2)=2）
  4. 计算顺序：自底向上（迭代）或自顶向下（递归+记忆化）

这种模式可推广至其他动态规划问题，如背包问题、最长公共子序列等。

六、总结与最佳实践

LeetCode爬楼梯问题虽简单，却蕴含了动态规划的核心思想。从递归到动态规划，再到矩阵快速幂的优化过程，展示了算法优化的典型路径。实际开发中，建议遵循以下原则：

  1. 优先选择时间空间平衡的解法：滚动数组优化是通用最优解
  2. 注意边界条件处理：如n=0或n=1时的特殊情况
  3. 理解优化本质：空间优化本质是消除冗余计算，矩阵快速幂本质是利用数学性质

通过深入理解此类问题，可提升对动态规划问题的分析能力，为解决更复杂的算法问题奠定基础。

最新文章