从斐波那契到爬楼梯：用Python三种方法搞定LeetCode 70题（附复杂度分析）

第一次在LeetCode上遇到爬楼梯问题时，我盯着屏幕上的台阶数n，脑海里闪过无数种组合方式。直到发现每次只能迈1或2个台阶的规则后，突然意识到——这不就是斐波那契数列换了个马甲吗？今天我们就用Python这把瑞士军刀，解剖这道看似简单却暗藏玄机的经典算法题。

1. 问题本质与数学建模

站在楼梯底部仰望n级台阶时，最后一步只有两种可能：从n-1级跨1阶，或从n-2级跨2阶。这个关键观察将问题转化为：

f(n) = f(n-1) + f(n-2)

这正是斐波那契数列的递推公式。让我们用数学归纳法验证几个基础案例：

台阶数n	可行方案	方案数f(n)
1	[1]	1
2	[1+1], [2]	2
3	[1+1+1], [1+2], [2+1]	3
4	[1+1+1+1], [1+1+2], [1+2+1], [2+1+1], [2+2]	5

这个建模过程揭示了算法设计的核心—— 将实际问题抽象为已知数学模型 。理解这一点，后续的代码实现就水到渠成了。

2. 递归解法：直观但低效

最直接的实现方式是递归，完美对应数学定义：

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

复杂度分析 ：

• 时间复杂度：O(2^n) —— 递归树呈指数级膨胀
• 空间复杂度：O(n) —— 递归栈深度

实际测试时，当n=40时计算时间已超过10秒。这是因为存在大量重复计算，比如计算f(5)时需要f(4)和f(3)，而f(4)又需要f(3)和f(2)，其中f(3)被计算了两次。

提示：面试时如果只给出这种解法，可能会被追问优化方案

3. 记忆化递归：空间换时间的艺术

引入缓存机制避免重复计算：

def climb_stairs_memo(n, memo={}):
    if n <= 2:
        return n
    if n not in memo:
        memo[n] = climb_stairs_memo(n-1, memo) + climb_stairs_memo(n-2, memo)
    return memo[n]

优化效果 ：

• 时间复杂度降为O(n) —— 每个子问题只计算一次
• 空间复杂度保持O(n) —— 需要存储所有中间结果

实测n=45时仅需0.03毫秒。这种 自上而下 的解法特别适合问题具有重叠子特性的场景。

4. 动态规划：从记忆化到迭代

将递归转为迭代，采用 自底向上 的填表法：

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

虽然时间复杂度仍为O(n)，但消除了递归开销。不过空间使用可以进一步优化——我们其实只需要前两个状态。

5. 滚动数组：极致的空间优化

只维护必要的中间变量：

def climb_stairs_optimal(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a + b
    return b

最终优化指标 ：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

这是面试官最期待的解法，体现了对问题本质的深刻理解。在Python中还可以用生成器实现更优雅的写法：

def fib_gen():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a + b

def climb_stairs(n):
    return next(x for i,x in enumerate(fib_gen()) if i==n)

6. 面试实战策略

当被问到这道题时，建议分阶段回答：

1. 问题分析 ：指出斐波那契数列的关联性
2. 逐步优化 ：
   • 先给出递归解法
   • 分析缺陷后引入记忆化
   • 转为动态规划
   • 最终空间优化
3. 扩展讨论 ：
   • 如果每次可以爬1/2/3个台阶？递推式变为f(n)=f(n-1)+f(n-2)+f(n-3)
   • 使用矩阵快速幂可将时间复杂度优化到O(log n)

# 快速幂解法示例
def matrix_pow(mat, power):
    result = [[1 if i==j else 0 for j in range(len(mat))] for i in range(len(mat))]
    while power > 0:
        if power % 2 == 1:
            result = matrix_mult(result, mat)
        mat = matrix_mult(mat, mat)
        power //= 2
    return result

def climb_stairs_matrix(n):
    if n <= 2: return n
    mat = [[1,1], [1,0]]
    return matrix_pow(mat, n)[0][0]

记住，面试官考察的不仅是解法，更是你 分析问题、优化方案的思维过程 。这道题就像算法世界的Hello World，简单却蕴含着动态规划的精髓。