从‘爬楼梯’到斐波那契：一个算法模型搞定LeetCode 70题与信息学奥赛真题
第一次接触LeetCode 70题"爬楼梯"时，很多人会惊讶地发现——这道看似简单的题目背后，隐藏着计算机科学中最优雅的数学模型之一。更令人惊喜的是，当你在信息学奥赛中遇到"爬楼梯"问题时，解题思路竟然如出一辙。这种跨越不同学习场景的算法复用，正是高效学习计算机科学的密钥。
1. 斐波那契数列：跨越千年的算法基石
1202年，意大利数学家斐波那契在《计算之书》中提出了一个看似简单的数列问题。谁能想到，800多年后，这个数列会成为算法竞赛和面试题库中的常客？斐波那契数列的定义简单明了：
F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) (n ≥ 2)但在计算机领域，这个数列展现出惊人的普适性。让我们看几个典型应用场景：
- 爬楼梯问题：每次可以迈1或2个台阶，n阶楼梯有多少种走法？
- 兔子繁殖问题：假设兔子永远不会死，每个月能生一对新兔子，n个月后有多少对兔子？
- 瓷砖铺设问题：用1×2的瓷砖铺2×n的地板，有多少种铺法？
提示：斐波那契数列的前10项为0,1,1,2,3,5,8,13,21,34,55。观察这些数字，你会发现它们频繁出现在各种组合问题中。
2. LeetCode 70题与信息学奥赛的"双生子"问题
2.1 LeetCode 70题：求职面试的标准模板
LeetCode上的"Climbing Stairs"是动态规划的入门必做题。题目描述简单直接：
问题描述：
假设你正在爬楼梯。需要n阶才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶？
示例：
输入：n = 3 输出：3 解释：有三种方法爬到第三阶 1. 1阶 + 1阶 + 1阶 2. 1阶 + 2阶 3. 2阶 + 1阶典型的解法是使用动态规划：
def climbStairs(n: int) -> int: 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]2.2 信息学奥赛版本：更注重算法效率
信息学奥赛中的爬楼梯问题（如OpenJudge NOI 2.2 3089）在本质上与LeetCode题目相同，但通常会有以下区别：
| 特性 | LeetCode 70题 | 信息学奥赛版本 |
|---|---|---|
| 输入规模 | 通常n≤45 | 可能n≤1000甚至更大 |
| 考察重点 | 基础DP思想 | 大数处理、空间优化 |
| 输出要求 | 返回整数 | 可能需要模运算或高精度输出 |
| 时间限制 | 较宽松 | 非常严格 |
奥赛版本的一个典型解法需要考虑空间优化：
def climbStairs_contest(n: int) -> int: if n <= 2: return n a, b = 1, 2 for _ in range(3, n+1): a, b = b, a + b return b3. 从递归到动态规划：四步拆解斐波那契问题
3.1 暴力递归：最直观的思路
初学者往往会首先想到递归解法：
def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2)但这种解法存在严重问题：
- 时间复杂度：O(2^n)，呈指数级增长
- 重复计算：fib(5)计算fib(4)和fib(3)，而fib(4)又计算fib(3)
3.2 记忆化搜索：用空间换时间
通过缓存已计算结果优化递归：
from functools import lru_cache @lru_cache(maxsize=None) def fib_memo(n): if n <= 1: return n return fib_memo(n-1) + fib_memo(n-2)优化效果：
- 时间复杂度降至O(n)
- 空间复杂度O(n)用于存储缓存
3.3 动态规划：自底向上的迭代
将递归转为迭代，避免栈溢出风险：
def fib_dp(n): if n <= 1: return n dp = [0]*(n+1) dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]3.4 空间优化：只保留必要状态
观察到当前状态只依赖前两个状态：
def fib_optimized(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n+1): a, b = b, a + b return b优化结果：
- 空间复杂度降至O(1)
- 时间复杂度保持O(n)
4. 斐波那契数列的数学之美与工程实践
4.1 通项公式与矩阵快速幂
斐波那契数列存在精确的闭式解（Binet公式）：
F(n) = (φ^n - ψ^n)/√5 其中φ=(1+√5)/2≈1.618，ψ=(1-√5)/2≈-0.618基于此，我们可以实现O(log n)时间复杂度的算法：
def fib_matrix(n): def matrix_pow(mat, power): result = [[1,0],[0,1]] # 单位矩阵 while power > 0: if power % 2 == 1: result = [[result[0][0]*mat[0][0]+result[0][1]*mat[1][0], result[0][0]*mat[0][1]+result[0][1]*mat[1][1]], [result[1][0]*mat[0][0]+result[1][1]*mat[1][0], result[1][0]*mat[0][1]+result[1][1]*mat[1][1]]] mat = [[mat[0][0]*mat[0][0]+mat[0][1]*mat[1][0], mat[0][0]*mat[0][1]+mat[0][1]*mat[1][1]], [mat[1][0]*mat[0][0]+mat[1][1]*mat[1][0], mat[1][0]*mat[0][1]+mat[1][1]*mat[1][1]]] power //= 2 return result if n == 0: return 0 mat = [[1,1],[1,0]] result = matrix_pow(mat, n-1) return result[0][0]4.2 实际工程中的注意事项
在真实项目或竞赛中处理斐波那契问题时，需要考虑：
大数处理：当n很大时，结果可能超出整型范围
- 解决方案：使用模运算（如结果对1e9+7取模）
精度问题：使用通项公式时浮点精度可能不足
- 解决方案：仅在小n时使用，大n用矩阵法或动态规划
多查询优化：如果需要多次查询不同n的值
- 解决方案：预处理前N个结果存入数组
# 预处理示例 max_n = 10**6 mod = 10**9+7 fib_pre = [0,1] for i in range(2, max_n+1): fib_pre.append((fib_pre[-1]+fib_pre[-2])%mod)5. 算法思维迁移：识别问题模式的实用技巧
斐波那契问题的核心特征是当前状态依赖于固定数量的前驱状态。识别这类问题的关键模式包括：
- 选择决策：在每个步骤有有限的选择（如爬楼梯选1或2阶）
- 无后效性：当前决策不影响之前的状态
- 重叠子问题：不同路径可能到达相同中间状态
其他可以用斐波那契模型解决的问题：
- 解码方式问题：数字串解码为字母（1→A，...，26→Z），"12"可解码为"AB"或"L"
- 多米诺骨牌覆盖：用2×1多米诺覆盖2×n棋盘
- 不相邻元素求和：从数组选不相邻元素求最大和
以解码问题为例的解法：
def numDecodings(s: str) -> int: if not s or s[0] == '0': return 0 n = len(s) dp = [0]*(n+1) dp[0], dp[1] = 1, 1 for i in range(2, n+1): if s[i-1] != '0': dp[i] += dp[i-1] if '10' <= s[i-2:i] <= '26': dp[i] += dp[i-2] return dp[n]在实际教学中，我常建议学生建立一个"问题模式-算法模型"的对应表。当遇到新问题时，先尝试识别其结构特征，再匹配已知的算法模式。这种方法在竞赛和面试中都极为高效。
