从斐波那契到爬楼梯：用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]）
用表格表示前几项的关系：
| 台阶数n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 走法数F(n) | 1 | 2 | 3 | 5 | 8 |
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.618Python实现：
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 c2. 成本最小化：每个台阶有体力成本，求最小成本路径
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. 调试技巧与常见错误
在实现动态规划时，这些陷阱需要注意：
- 边界条件错误：忘记处理n=0或n=1的情况
- 索引偏移：Python列表从0开始，与问题描述的从1开始容易混淆
- 空间优化遗漏：没有发现只需要前两个状态的规律
- 整数溢出：当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题，提交时要注意：
- 预处理前几个结果加速
- 使用位运算代替模运算
- 循环展开减少迭代次数
优化后的终极版本：
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的变种题，最终通过观察斐波那契数列模某个数的周期性解决了问题。
