1. 问题引入为什么爬楼梯是经典算法题第一次接触爬楼梯问题是在刷LeetCode的时候题目描述简单到让人怀疑是不是看错了假设你正在爬楼梯需要n阶才能到达楼顶每次可以爬1或2个台阶问有多少种不同的方法可以爬到楼顶这个问题看似简单却包含了算法设计的精髓。我记得当时用递归写完提交后系统提示超时这才意识到原来简单的题目里藏着这么多门道。这个问题之所以经典是因为它完美展现了算法优化的完整路径。从最直观的递归解法到引入记忆化搜索再到动态规划最后还能用数学方法求解。每个优化步骤都能带来数量级的性能提升这对理解算法本质特别有帮助。就像搭积木一样我们可以从最基础的解法开始一步步搭建出更高效的解决方案。在实际工作中这类问题也很常见。比如支付系统的组合支付方案、物流配送的路径选择等都可以抽象成类似的模型。理解了这个问题的解法演进就能举一反三应用到更多场景中。2. 递归解法最直观的思路2.1 基础递归实现当我第一次尝试解决这个问题时最自然的想法就是用递归。因为要到达第n阶台阶要么从n-1阶跨1步上来要么从n-2阶跨2步上来。所以解法数就是这两种情况的和。写成代码就是def climbStairs(n): if n 1 or n 2: return n return climbStairs(n-1) climbStairs(n-2)这个解法虽然简单明了但实际运行时会发现当n稍大比如40时计算速度就会变得非常慢。这是因为递归树中存在大量重复计算。比如计算climbStairs(5)时需要计算climbStairs(4)和climbStairs(3)而计算climbStairs(4)时又要计算climbStairs(3)和climbStairs(2)这里的climbStairs(3)就被重复计算了。2.2 递归的时间复杂度分析递归解法的时间复杂度是指数级的O(2^n)因为每个调用都会产生两个新的调用。空间复杂度是O(n)由递归调用栈的深度决定。这种效率在实际应用中是完全不可接受的。我记得第一次提交这个解法时LeetCode直接给出了超时错误这让我意识到必须寻找更优的解法。3. 记忆化递归消除重复计算3.1 引入备忘录优化既然基础递归的问题在于重复计算那么很自然的优化思路就是记住已经计算过的结果。这就是所谓的记忆化搜索Memoization。我们可以用一个数组来存储已经计算过的值def climbStairs(n, memoNone): if memo is None: memo [0] * (n 1) if n 1 or n 2: return n if memo[n] 0: return memo[n] memo[n] climbStairs(n-1, memo) climbStairs(n-2, memo) return memo[n]这个优化带来的提升是巨大的。现在每个子问题只需要计算一次时间复杂度降到了O(n)空间复杂度仍然是O(n)因为需要存储备忘录。在实际测试中n40时递归解法需要几秒甚至更久而记忆化版本几乎是瞬间完成。3.2 记忆化搜索的局限性虽然记忆化递归解决了重复计算的问题但它仍然使用递归调用当n很大时比如几万还是可能遇到栈溢出问题。此外递归调用本身也有一定的开销。这促使我们思考能否完全摆脱递归用迭代的方式实现同样的效果。4. 动态规划自底向上的解法4.1 标准动态规划实现动态规划DP是解决这类问题的标准方法。与记忆化递归的自顶向下不同DP采用自底向上的方式先解决小问题再逐步构建大问题的解。对于爬楼梯问题DP解法非常直观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)。虽然看起来和记忆化递归的效率相同但实际上迭代的DP解法通常比递归更快因为没有函数调用的开销而且更容易优化。4.2 DP解法的优势动态规划的最大优势在于它清晰地展现了问题的子结构。我们可以明确看到每个状态dp[i]只依赖于前两个状态dp[i-1]和dp[i-2]。这种特性提示我们可能可以进行进一步的空间优化。此外DP的思维模式可以推广到更复杂的问题中比如带权重的爬楼梯问题每步有不同的代价或者有更多步数选择比如可以走1、2或3步的变种。5. 空间优化滚动数组技术5.1 优化空间复杂度仔细观察DP解法我们会发现实际上不需要存储整个dp数组因为每个状态只依赖于前两个状态。因此可以用两个变量来交替存储这些值def climbStairs(n): if n 1: return 1 first, second 1, 2 for _ in range(3, n 1): third first second first, second second, third return second这个优化将空间复杂度从O(n)降到了O(1)而时间复杂度保持不变。在实际应用中这种优化对于内存受限的环境特别有价值。我曾在嵌入式系统中实现过类似算法这种空间优化使得算法可以在资源有限的设备上运行。5.2 滚动数组的通用性滚动数组技术不仅适用于爬楼梯问题它在许多DP问题中都有应用。只要状态转移只依赖于有限个前驱状态就可以用固定数量的变量来代替整个DP数组。这种技术在处理大规模数据时尤为重要可以显著减少内存使用。6. 数学解法斐波那契与矩阵快速幂6.1 斐波那契数列的关联细心的读者可能已经发现爬楼梯问题的解实际上就是斐波那契数列的变种F(1)1, F(2)2, F(n)F(n-1)F(n-2)。这个发现让我们可以应用数学上对斐波那契数列的研究成果来进一步优化解法。6.2 矩阵快速幂解法斐波那契数列有一个基于矩阵乘法的对数时间解法。关键是将递推关系表示为矩阵形式[F(n) ] [0 1][F(n-1)] [F(n-1)] [1 1][F(n-2)]通过矩阵快速幂技术可以在O(log n)时间内计算出结果def multiply(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]] ] def matrix_pow(mat, power): result [[1, 0], [0, 1]] # 单位矩阵 while power 0: if power % 2 1: result multiply(result, mat) mat multiply(mat, mat) power // 2 return result def climbStairs(n): if n 1: return 1 mat [[0, 1], [1, 1]] return matrix_pow(mat, n)[1][1]这个解法的时间复杂度是O(log n)空间复杂度是O(1)。虽然实现起来比前几种方法复杂但对于非常大的n比如n1e18这是唯一可行的解法。6.3 通项公式解法斐波那契数列还有通项公式Binet公式F(n) (φ^n - ψ^n)/√5其中φ(1√5)/2ψ(1-√5)/2由于|ψ|1当n较大时ψ^n可以忽略因此可以简化为F(n) round(φ^n/√5)对应的Python实现def climbStairs(n): sqrt5 5**0.5 phi (1 sqrt5) / 2 return int(round(phi**(n 1) / sqrt5))需要注意的是由于浮点数精度限制当n很大时这个解法可能会有精度误差。在实际应用中矩阵快速幂通常是更可靠的选择。