CS-Notes 剑指 Offer 10.1 斐波那契数列：从重复递归到三种递推解法的完整剖析

本篇基于 CS-Notes 仓库的剑指 Offer 动态规划题解 10.1 斐波那契数列，围绕"求斐波那契数列第 n 项（n <= 39）"这一经典动态规划入门题，拆解朴素递归重复计算的根源，并完整给出数组 DP、O(1) 空间优化、预计算表三种实现及其复杂度权衡，最后结合仓库中同族题解（矩形覆盖、跳台阶、变态跳台阶）说明该递推模型如何贯穿整个动态规划章节。

题目描述

题目要求：求斐波那契数列的第 n 项，约束条件为 n <= 39。

其数学定义为分段函数：

即：

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

在仓库中，本题与 10.2 矩形覆盖、10.3 跳台阶、10.4 变态跳台阶 共同构成剑指 Offer 动态规划专题的第一组题目，它们全部收录在 剑指 Offer 题解 - 目录 的"动态规划"章节下。

为什么朴素递归低效：重复子问题

最直接的写法是照抄递推式的递归，但它会重复求解相同的子问题。以计算 f(4) 为例：计算 f(4) 需要 f(3) 和 f(2)，而计算 f(3) 又需要 f(2) 和 f(1)，可以看到 f(2) 被计算了两次；随着 n 增大，重复量呈指数级膨胀。

原文档给出的核心论断是：递归是将一个问题划分成多个子问题求解，动态规划也是如此，但动态规划会把子问题的解缓存起来，从而避免重复求解子问题。这一句也是仓库中 Leetcode 题解 - 动态规划 开篇的总纲——"递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算"。

解法一：自底向上 DP 数组，O(N) 时间 O(N) 空间

用数组缓存每一项的结果，自底向上递推，避免递归的重复计算：

public int Fibonacci(int n) {
    if (n <= 1)
        return n;
    int[] fib = new int[n + 1];
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    return fib[n];
}

逐点说明：

• if (n <= 1) return n; 对应分段函数的两个基础情形 f(0) = 0、f(1) = 1，同时天然防止越界；
• fib 数组长度为 n + 1，下标即项数，fib[i] 表示第 i 项的值，这是典型的"状态定义 + 状态转移"结构；
• 状态转移 fib[i] = fib[i - 1] + fib[i - 2] 与递推式一一对应，每个状态只计算一次；
• 时间复杂度 O(N)，空间复杂度 O(N)。

解法二：滚动变量，把空间降到 O(1)

观察到第 i 项只与第 i-1 项和第 i-2 项有关，状态转移的"窗口"宽度固定为 2，因此无需保存整个数组，用两个变量滚动记录前两项即可，将空间复杂度由 O(N) 降低为 O(1)：

public int Fibonacci(int n) {
    if (n <= 1)
        return n;
    int pre2 = 0, pre1 = 1;
    int fib = 0;
    for (int i = 2; i <= n; i++) {
        fib = pre2 + pre1;
        pre2 = pre1;
        pre1 = fib;
    }
    return fib;
}

其中：

• pre2、pre1 分别滚动保存 f(i-2)、f(i-1)，初值 0 和 1 对应 f(0)、f(1)；
• 每次迭代先算出 fib = pre2 + pre1，再整体前移一步（pre2 = pre1; pre1 = fib;），完成状态转移；
• 时间复杂度仍是 O(N)，空间复杂度降为 O(1)。

这种"状态只依赖前 k 项时用 k 个变量滚动"的手法，在仓库其他题解中被反复复用，例如 Leetcode 题解 - 动态规划 中"爬楼梯"一题的 climbStairs 实现就是同样的 pre2/pre1 双变量模式。

解法三：预计算表，O(1) 查询

由于题目约束 n < 40，取值空间极小，可以在对象初始化时一次性算好前 40 项，之后每次查询直接取表，以 O(1) 时间复杂度返回第 n 项：

public class Solution {

    private int[] fib = new int[40];

    public Solution() {
        fib[1] = 1;
        for (int i = 2; i < fib.length; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
    }

    public int Fibonacci(int n) {
        return fib[n];
    }
}

要点：

• 预计算放在构造函数中完成，Solution 实例化后 Fibonacci(n) 就是一次数组下标访问；
• 数组长度固定为 40（题目保证 n <= 39），无需任何边界判断；
• 从源码结构看，该方案把 O(N) 的一次性成本摊到了查询路径之外，适合"同一实例被多次查询、n 上限已知且很小"的面试题型；若接口允许 n 超过 39，则需改回动态计算。

三种解法对比

解法	时间复杂度	空间复杂度	适用场景
朴素递归（反例）	指数级（大量重复计算）	O(N) 递归栈	仅作对照，不可提交
DP 数组	O(N)	O(N)	通用，且保留完整序列便于调试
滚动变量	O(N)	O(1)	只需要最终结果时的最优常规模板
预计算表	O(1) 查询（均摊 O(N) 建表）	O(1)（固定 40 项）	n 上限已知且极小、多次查询

面试中通常的答法是：先指出朴素递归的重复子问题，再给出 O(N)/O(1) 的滚动解法作为主解，最后主动补充"n < 40 可以预计算"这一针对题目约束的优化点，体现对边界条件的敏感度。

同族扩展：同一个递推模型贯穿动态规划章节

本题的状态转移 f(n) = f(n-1) + f(n-2) 并非孤立技巧，仓库中多个题解共享这一模型：

• 10.2 矩形覆盖：用 n 个 2*1 小矩形覆盖 2*n 大矩形，其递推公式同样化为 f(n) = f(n-1) + f(n-2)（基础情形 n=1 时为 1、n=2 时为 2），题解直接采用了与本文解法二一致的 pre2/pre1 滚动写法；
• 10.3 跳台阶：青蛙一次跳 1 级或 2 级，跳 n 级台阶的方法数递推也是 f(n) = f(n-1) + f(n-2)；
• 10.4 变态跳台阶：允许跳 1 到 n 级时，通过 f(n) - f(n-1) = f(n-1) 推导出 f(n) = 2 * f(n-1)，答案变为 2 的 (n-1) 次方，展示了同一框架下如何进一步化简；
• Leetcode 题解 - 动态规划 中的"爬楼梯"（70. Climbing Stairs）、"强盗抢劫"（198. House Robber，状态转移改为取最大值）也都是"拆子问题 + 缓存状态"思想的变体，其中爬楼梯一题的 O(1) 空间优化注释与本文解法二的思路完全一致。

小结

斐波那契数列是动态规划的入门题，10.1 斐波那契数列 一文给出了完整的三档实现：DP 数组缓存子问题解（O(N) 时间 / O(N) 空间）、双变量滚动（O(N) 时间 / O(1) 空间）、以及利用 n <= 39 约束的预计算表（O(1) 查询）。掌握"识别重复子问题 → 定义状态与转移 → 按空间与查询模式选优化"这条主线后，可以直接迁移到仓库动态规划专题中的矩形覆盖、跳台阶、爬楼梯等题目上。