从斐波那契到爬楼梯：用Python动态规划解决经典问题，附LeetCode 70题保姆级解析

从斐波那契到爬楼梯：用Python动态规划解决经典问题，附LeetCode 70题保姆级解析

每次看到LeetCode上那些标着"简单"却让人抓耳挠腮的题目，总让我想起自己初学算法时的窘迫。特别是第70题"爬楼梯"，表面看是个小学数学题，实则暗藏玄机。今天我们就来拆解这个经典问题，看看它如何与斐波那契数列产生奇妙关联，以及如何用动态规划优雅解决。

1. 问题本质与数学建模

站在楼梯前的小明可能不知道，他面临的其实是个历史悠久的数学问题。当台阶数n=10时，走法总数恰好是斐波那契数列的第11项（如果从F(0)=1开始计数）。这种巧合背后是相同的递推关系：

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

为什么这个公式成立？想象你站在第n级台阶上，上一步只能来自：

• 从n-1级跨1步
• 从n-2级跨2步

这两种选择互斥且完备，因此总方法数就是两者之和。这就是重叠子问题特性——每个台阶的解都依赖于更小台阶的解。

边界条件需要特别注意：

• n=1时只有1种走法（[1]）
• n=2时有2种走法（[1,1]和[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)

这个解法的时间复杂度是O(2^n)，因为每次调用都会分裂成两个子调用。当n=40时，计算量已经超过万亿次。

动态规划通过存储中间结果来优化：

def climb_stairs(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)，空间复杂度也是O(n)。但观察状态转移可以发现，我们只需要保存前两个状态：

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

这种优化将空间复杂度降至O(1)，是面试官最期待的写法。

3. 复杂度分析与数学解法

除了动态规划，这个问题还有几种有趣的解法：

矩阵快速幂（时间复杂度O(log 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 climb_stairs(n): if n <= 2: return n mat = [[1,1],[1,0]] return matrix_pow(mat, n)[0][0]

通项公式法（时间复杂度O(1)）： 斐波那契数列有精确的闭式解：

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

Python实现：

import math def climb_stairs(n): sqrt5 = math.sqrt(5) phi = (1 + sqrt5) / 2 return int((phi**(n+1) - (-phi)**(-n-1))/sqrt5)

注意：浮点数精度限制使得这种方法在n>70时可能产生误差

4. 变种问题与实际应用

掌握了基础解法后，可以尝试这些常见变种：

1. 步长变化：如果还能一次跨3步，递推式变为F(n)=F(n-1)+F(n-2)+F(n-3)

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

2. 成本最小化：每个台阶有体力成本，求最小成本路径

def min_cost_climbing(costs): n = len(costs) dp = [0]*n dp[0], dp[1] = costs[0], costs[1] for i in range(2, n): dp[i] = min(dp[i-1], dp[i-2]) + costs[i] return min(dp[-1], dp[-2])

3. 空间约束：在O(1)空间下处理大规模n值（使用生成器）：

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

这些变种在电商优惠券组合、机器人路径规划等领域都有实际应用。比如优惠券满减问题，就可以建模为"用给定面额的券组合出目标金额的方法数"。

5. 调试技巧与常见错误

在实现动态规划时，这些陷阱需要注意：

1. 边界条件错误：忘记处理n=0或n=1的情况
2. 索引偏移：Python列表从0开始，与问题描述的从1开始容易混淆
3. 空间优化遗漏：没有发现只需要前两个状态的规律
4. 整数溢出：当n很大时，结果可能超过普通整数范围

调试时可以：

• 打印dp表格检查中间结果
• 用小规模测试用例手动验证
• 比较递归和迭代版本的结果

# 调试示例 def test(): for n in range(1, 10): recursive = climb_stairs_recursive(n) dp = climb_stairs_dp(n) assert recursive == dp, f"Failed at n={n}" print("All tests passed!")

6. LeetCode实战与优化

针对LeetCode 70题，提交时要注意：

1. 预处理前几个结果加速
2. 使用位运算代替模运算
3. 循环展开减少迭代次数

优化后的终极版本：

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

对于特别大的n（比如1e18），需要使用快速幂算法或者找规律发现周期性。我在一次周赛中遇到过n上限为1e100的变种题，最终通过观察斐波那契数列模某个数的周期性解决了问题。