LC509. 斐波那契数

题目描述

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。 示例 1： 输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2： 输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3： 输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3 提示： 0 <= n <= 30

题目解析

好的，没问题。我是 AlgoMooc 的算法老师，咱们这就用最轻松、最易懂的方式，把这道经典的“斐波那契数”给彻底搞明白。

---

题目在说什么

这道题其实就是在讲一个“生兔子”的故事，只不过是用数学的方式写出来了。

想象一下，有一对刚出生的兔子。它们要长大一个月才能生小兔子。之后，每个月都会生一对新的小兔子。而且，新生的兔子也要等一个月才能生。那么，每个月总共有多少对兔子呢？

这个兔子数量的序列，就是斐波那契数列。它的规则特别简单： 1. 第一个月（n=0）：兔子还没出生，所以是 0 对。 2. 第二个月（n=1）：有了第一对兔子，所以是 1 对。 3. 第三个月（n=2）：第一对兔子成年了，生了一对新的，所以总共有 1 + 1 = 2 对。 4. 第四个月（n=3）：第一对兔子继续生，第二对兔子还没成年，所以总共有 2 + 1 = 3 对。 5. 第五个月（n=4）：第一对、第二对都成年了，都能生，所以是 3 + 2 = 5 对。

你看，规律就出来了：这个月的兔子总数 = 上个月的兔子总数 + 上上个月的兔子总数。也就是 F(n) = F(n-1) + F(n-2)。

题目给你的 n，就是问第 n 个月有多少对兔子。比如 n=4，答案就是 3。

---

思路是怎么来的

这道题最直接的思路，就是“模仿”这个生兔子的过程。

思路一：递归——像照镜子一样

你可能会想：“这还不简单？我直接按照规则写个公式不就行了？”

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

那 F(n-1) 又等于什么呢？等于 F(n-2) + F(n-3)。F(n-2) 又等于 F(n-3) + F(n-4)…… 就这样一直问下去，问到什么时候是个头呢？

问到 F(0) 和 F(1) 的时候，我们就知道答案了，因为题目告诉我们 F(0)=0，F(1)=1。

这种“自己调用自己”的解决问题的方法，就叫递归。就像你站在两面镜子中间，镜子里会反射出无数个你，一层套一层。递归就是这种“套娃”式的思考方式。

但是，递归有个大问题：太笨了，会做大量重复的计算。

比如，要算 F(5)，它需要算 F(4) 和 F(3)。算 F(4) 又需要算 F(3) 和 F(2)。你看，F(3) 被算了两次！当 n 变大时，这种重复计算会呈指数级增长，慢得无法接受。

思路二：记忆化搜索——给递归加个小本本

怎么解决递归的“笨”呢？很简单，给它一个小本本（一个数组，叫 memo）。

每次要算 F(k) 的时候，先看看小本本上有没有记过这个结果。如果有，直接拿来用，不用再算一遍了。如果没有，就算出来，然后记在小本本上，下次再用。

这就是记忆化搜索。它还是递归的思路，但是通过“记忆”避免了重复劳动，效率大大提升。

思路三：动态规划——从前往后，一步一个脚印

记忆化搜索虽然好，但还是有点“从上往下”思考的感觉（先想大的，再想小的）。我们能不能换个思路，从最小的开始，一步一步往上算呢？

当然可以！这就是动态规划。

我们直接拿一个数组 dp 来记录结果。dp[0] = 0，dp[1] = 1，这是最基础的两个数。然后，我们根据规则 dp[2] = dp[1] + dp[0]，算出 dp[2]。再根据 dp[3] = dp[2] + dp[1]，算出 dp[3]…… 一直算到 dp[n] 为止。

这个过程就像盖楼一样，从地基（dp[0]、dp[1]）开始，一层一层往上盖，每一步都依赖下面已经盖好的楼层，非常稳健。

---

代码逐步拆解

我们重点来看参考代码里最推荐的动态规划版本（myFib3 方法）。

class Solution {
    public int fib(int N) {
        // 1. 处理特殊情况
        if (N < 2) return N;

        // 2. 创建 dp 数组，并初始化
        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = 1;

        // 3. 从 i=2 开始，一步步计算
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 4. 返回最终结果
        return dp[N];
    }
}

逐行解释：

1. `if (N < 2) return N;`