LeetCode 70. 爬楼梯：三种解法（递归/记忆化/动态规划）的详细对比与优化实战

LeetCode 70. 爬楼梯从递归到动态规划的算法进化之旅每次面对这道经典题目时总让我想起初学算法时的困惑——为什么看似简单的爬楼梯问题能成为动态规划的入门必修课今天我们就用工程师的视角拆解这道题背后的算法思维进化史。1. 问题本质与暴力递归解法当我们第一次遇到爬楼梯问题时最直观的想法往往是穷举所有可能的走法。假设楼梯有n级台阶每次可以跨1步或2步这个问题本质上是在问有多少种不同的序列组合能让步数之和恰好等于n1.1 递归关系建立仔细观察会发现到达第n级台阶只有两种可能从第n-1级跨1步从第n-2级跨2步这自然引出了著名的斐波那契递推关系def climb_stairs(n): if n 1: return 1 if n 2: return 2 return climb_stairs(n-1) climb_stairs(n-2)1.2 递归解法的问题虽然这种解法简洁明了但实际运行时会发现严重的性能问题。以n5为例递归树的调用过程如下climb_stairs(5) ├── climb_stairs(4) │ ├── climb_stairs(3) │ │ ├── climb_stairs(2) │ │ └── climb_stairs(1) │ └── climb_stairs(2) └── climb_stairs(3) ├── climb_stairs(2) └── climb_stairs(1)可以看到climb_stairs(3)被计算了两次这种重复计算随着n增大呈指数级增长。时间复杂度分析解法时间复杂度空间复杂度暴力递归O(2^n)O(n)提示当n40时递归解法在普通计算机上可能需要几分钟才能完成计算完全无法满足算法竞赛的要求。2. 记忆化搜索给递归加上缓存面对递归解法的性能瓶颈我们很自然地想到能否避免重复计算这就是记忆化(Memoization)技术的核心思想。2.1 实现记忆化递归我们引入一个数组来存储已经计算过的结果def climb_stairs_memo(n, memoNone): if memo is None: memo [0] * (n 1) if n 1: return 1 if n 2: return 2 if memo[n] 0: return memo[n] memo[n] climb_stairs_memo(n-1, memo) climb_stairs_memo(n-2, memo) return memo[n]2.2 复杂度分析记忆化后每个子问题只需要计算一次解法时间复杂度空间复杂度记忆化递归O(n)O(n)虽然时间复杂度降到了线性但递归调用栈仍然需要O(n)的空间。对于特别大的n(如1e6)这可能导致栈溢出。3. 动态规划自底向上的迭代为了彻底解决递归的空间问题我们可以采用动态规划(Dynamic Programming)的迭代方法。3.1 基础DP实现def climb_stairs_dp(n): if n 1: return 1 dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这种实现方式直观展示了动态规划填表的过程但空间复杂度仍是O(n)。3.2 空间优化滚动数组观察状态转移方程发现当前状态只依赖前两个状态因此可以进一步优化def climb_stairs_dp_opt(n): if n 1: return 1 a, b 1, 2 for _ in range(3, n1): a, b b, a b return b优化后的空间复杂度降到了O(1)这是大多数面试官期望看到的最终解法。4. 数学解法通向O(1)复杂度对于追求极致的开发者还可以探索数学解法。爬楼梯问题本质上就是求解斐波那契数列而斐波那契数列有通项公式F(n) (φ^n - ψ^n)/√5其中φ(1√5)/2ψ(1-√5)/2但由于浮点数精度问题这种解法在实际编程中并不常用。更实用的O(logn)解法是利用矩阵快速幂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]] ] 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 climb_stairs_math(n): if n 1: return 1 mat [[1,1],[1,0]] return matrix_pow(mat, n)[0][0]5. 实战对比与选择建议在实际面试或竞赛中如何选择合适的解法以下是各方法的对比表格解法类型时间复杂度空间复杂度适用场景实现难度暴力递归O(2^n)O(n)教学理解★★记忆化搜索O(n)O(n)递归思维过渡★★★基础DPO(n)O(n)教学演示★★滚动数组DPO(n)O(1)面试最佳★★★矩阵快速幂O(logn)O(1)理论最优★★★★对于日常编程和面试滚动数组DP是最佳选择足够高效线性时间常数空间易于实现10行左右代码展示能力体现了空间优化思维注意在真正面试时建议先提出递归解法然后分析其问题再逐步优化到DP解法最后讨论可能的数学优化。这种解题思路的演进过程比直接给出最优解更能展示算法思维能力。6. 变种问题拓展掌握了基础爬楼梯问题后可以尝试以下变种来深化理解三步问题每次可以爬1、2或3个台阶def climb_stairs_3(n): if n 3: return n a, b, c 1, 2, 4 for _ in range(4, n1): a, b, c b, c, a b c return c带成本爬楼梯每个台阶有成本求最小成本路径def min_cost_climbing(cost): n len(cost) a, b 0, 0 for i in range(2, n1): a, b b, min(a cost[i-2], b cost[i-1]) return b禁止某些台阶给定不能踩的台阶列表求可行路径数这些变种问题在LeetCode上都能找到对应题目是练习动态规划思维的绝佳材料。