第 51 课 - 斐波那契数列与爬楼梯

所属模块： 动态规划 难度： beginner 标签： fibonacci, climb-stairs, overlapping 课程导航： 上一课：动态规划入门 | 下一课：背包问题

学习目标

通过学习本节课，你将能够：

理解斐波那契数列的定义及其朴素递归解法的问题所在。
掌握使用“带备忘录的递归”或“自底向上的动态规划”高效解决斐波那契问题。
将“爬楼梯”问题建模为一个斐波那契数列问题。
学会优化动态规划解法的空间复杂度。

核心概念

想象一下，你正站在一段楼梯的底部，每次你只能向上迈1级或2级台阶。如果这段楼梯共有 n 级，问你有多少种不同的方法可以爬到顶部？

这个问题听起来很生活化，但它和另一个著名的数学问题——斐波那契数列——有着深刻的联系。

1. 斐波那契数列

斐波那契数列由以下规则定义：

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

意思是，当前项的值等于前两项之和。这个数列在自然界中广泛存在（如植物的叶序、花瓣数），也是学习动态规划的经典入门案例。

朴素递归解法及其问题： 我们可以直接按照定义写出递归函数。但这种方法效率极低，因为存在大量的重叠子问题。

让我们计算 F(5)：

F(5) = F(4) + F(3)
     = (F(3)+F(2)) + (F(2)+F(1))
     = ((F(2)+F(1)) + (F(1)+F(0))) + ((F(1)+F(0)) + F(1))
     = ...

你会发现，F(3), F(2), F(1), F(0) 被反复计算了很多次。当 n 变大时，计算量呈指数级增长，程序会变得非常慢甚至无法运行。

2. 动态规划思想

动态规划的核心思想之一就是 “记住已经解决的子问题”。

对于斐波那契问题，我们可以：

带备忘录的递归（自顶向下）：在递归过程中，用一个数组（或字典）记录下每个 F(i) 的计算结果。下次需要时直接查表，避免重复计算。
动态规划迭代（自底向上）：从最小的子问题开始，一步步构建更大的解。我们知道 F(0) 和 F(1)，就可以计算 F(2)，然后用 F(1) 和 F(2) 计算 F(3)，以此类推，直到得到 F(n)。

3. 爬楼梯问题建模

回到爬楼梯问题。假设到达第 n 级台阶有 dp(n) 种方法。

要到达第 n 级，最后一步要么是从第 n-1 级迈1步上来，要么是从第 n-2 级迈2步上来。
因此，到达第 n 级的方法数，等于到达第 n-1 级的方法数加上到达第 n-2 级的方法数。
数学表达：dp(n) = dp(n-1) + dp(n-2)。

看，这和斐波那契数列的递推公式 F(n) = F(n-1) + F(n-2) 完全一致！我们只需要确定边界条件：dp(1)=1, dp(2)=2（这对应着斐波那契数列的 F(2)=1, F(3)=2，只是起始索引不同）。所以，爬楼梯问题本质上就是求解一个斐波那契数列。

代码示例

示例1：朴素递归（效率低下，仅供理解定义）

def fib_recursive(n):
    """
    使用朴素递归计算斐波那契数列第n项（从0开始）
    时间复杂度：O(2^n) - 非常慢！
    空间复杂度：O(n) - 递归栈深度
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# 测试
n = 5
print(f"朴素递归计算 F({n}) = {fib_recursive(n)}")  # 输出：5
# 注意：当n=40左右时，计算会明显变慢。

示例2：带备忘录的递归（自顶向下动态规划）

def fib_memoization(n, memo={}):
    """
    使用备忘录（缓存）优化递归，避免重复计算
    时间复杂度：O(n)
    空间复杂度：O(n) - 存储所有子问题结果 + 递归栈深度
    """
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    memo[n] = fib_memoization(n - 1, memo) + fib_memoization(n - 2, memo)
    return memo[n]

# 测试
n = 40
print(f"带备忘录递归计算 F({n}) = {fib_memoization(n)}")  # 输出：102334155，速度快得多

示例3：动态规划迭代解法（自底向上）

def climb_stairs(n):
    """
    解决爬楼梯问题：每次可以爬1或2级，求爬到第n级有多少种方法。
    本质是斐波那契数列，F(0)=0, F(1)=1, F(2)=1, ...
    爬楼梯：dp[1]=1, dp[2]=2， 对应 F(2)=1, F(3)=2
    我们直接从底向上计算。

    时间复杂度：O(n)
    空间复杂度：O(n) - 使用了一个数组存储所有中间状态
    """
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    # dp[i] 表示爬到第 i 级的方法数
    dp = [0] * (n + 1)
    dp[1] = 1  # 只有一种方式：爬1级
    dp[2] = 2  # 两种方式：1+1 或 2
    
    # 从第3级开始，利用状态转移方程计算
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# 测试
stairs = 10
print(f"爬 {stairs} 级楼梯有 {climb_stairs(stairs)} 种方法")  # 输出：89

示例4：空间优化后的动态规划

def climb_stairs_optimized(n):
    """
    空间优化版本：我们只关心前两个状态，无需存储整个数组。
    时间复杂度：O(n)
    空间复杂度：O(1)
    """
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    prev2 = 1  # 相当于 dp[i-2]
    prev1 = 2  # 相当于 dp[i-1]
    current = 0
    
    for i in range(3, n + 1):
        current = prev1 + prev2
        # 更新状态，为下一次迭代做准备
        prev2 = prev1
        prev1 = current
    
    return current

# 测试
stairs = 10
print(f"空间优化后，爬 {stairs} 级楼梯有 {climb_stairs_optimized(stairs)} 种方法")  # 输出：89

实践练习

练习1：斐波那契数列（基础）

题目： 编写一个函数，输入一个非负整数 n，返回斐波那契数列的第 n 项（定义 F(0)=0, F(1)=1, F(2)=1, F(3)=2...）。要求使用时间复杂度为 O(n) 的方法。 输入示例： n = 10 预期输出： 55

练习2：爬楼梯方案数（应用）

题目： 你正在爬一个有 n 级台阶的楼梯。每次你可以爬 1 级或 2 级。但是，你不能连续两次都爬 2 级（即不允许“2,2”这种走法）。请问有多少种不同的爬到楼顶的方案？（注意：n=0 时，方案数为1，表示“原地不动”也算一种方案） 提示： 这个问题的状态转移会略有变化，需要思考 dp[i] 是如何由 dp[i-1] 和 dp[i-2] 推导而来的，并且要考虑到连续2级的限制。 输入示例： n = 4 预期输出： 5 （解释：1,1,1,1; 1,1,2; 1,2,1; 2,1,1; 2,2 是不允许的，所以有效方案为前4种？不对，2,2确实不允许，所以是1,1,1,1; 1,1,2; 1,2,1; 2,1,1，只有4种？等待验证，题目可能需要更清晰的建模。或许我们可以用另一个状态变量。）

练习3：爬楼梯变种（进阶）

题目： 现在你每次可以爬 1 级、2 级或 3 级台阶。编写一个函数，计算爬到第 n 级有多少种不同的方法。 提示： 思考状态转移方程会发生什么变化？边界条件 dp(1), dp(2), dp(3) 应该如何设置？ 输入示例： n = 5 预期输出： 13 （可以自行枚举验证：1,1,1,1,1; 1,1,1,2; 1,1,2,1; 1,2,1,1; 2,1,1,1; 1,1,3; 1,3,1; 3,1,1; 1,2,2; 2,1,2; 2,2,1; 2,3; 3,2，共13种）

常见错误

边界条件处理错误：斐波那契数列中 F(0) 和 F(1) 的值，爬楼梯中 dp(1) 和 dp(2) 的值是递推的起点，必须正确定义，否则整个结果都会错误。
滥用朴素递归：对于稍大的 n（如 >35），朴素递归的解法会导致程序卡死或栈溢出。要养成使用“记忆化”或“迭代”DP的习惯。
索引混淆：斐波那契数列的常见定义从 F(0) 或 F(1) 开始，而爬楼梯问题通常从第1级开始。在建模时，注意将问题索引与标准数列索引对齐，否则公式会出错。例如，爬楼梯的 dp[1]=1, dp[2]=2 对应的是斐波那契的 F(2)=1, F(3)=2。
状态转移方程不清晰：在更复杂的问题中，要确保你真正理解“到达当前状态的最后一步是如何决策的”，从而正确写出转移方程，而不是死记硬背公式。

小结

本节课我们通过斐波那契数列和爬楼梯这两个经典问题，学习了动态规划的入门应用。

问题建模：爬楼梯问题可以完美地映射到斐波那契数列，这体现了将实际问题抽象为数学模型的能力。
重叠子问题：朴素递归之所以低效，是因为同一个子问题被计算了无数次。动态规划通过存储子问题的解来避免这种重复工作。
状态转移方程：dp[i] = dp[i-1] + dp[i-2] 是本节课的核心。它清晰地定义了当前状态与之前状态之间的依赖关系。
两种实现方式：“自顶向下”的带备忘录递归和“自底向上”的迭代法都是有效的DP实现。后者通常空间效率更高且更容易优化。
空间优化：在迭代法中，如果当前状态只依赖于前两个状态，我们可以只用几个变量来代替数组，将空间复杂度从 O(n) 降到 O(1)。

掌握了这些思想，你就为学习更复杂的动态规划问题（如背包问题、最长公共子序列等）打下了坚实的基础。在下一课中，我们将进入动态规划的另一个经典领域——背包问题。

练习编辑器

rust