0509.斐波那契数

难度：🟢 简单

标签：动态规划、记忆化搜索、数学、递归

链接：509. 斐波那契数

题目描述

斐波那契数 （通常用 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

解题思路

核心思想

本题是求解斐波那契数列的第 n 项，是动态规划的入门级问题。根据定义，第 n 项的值完全取决于其前两项 F(n-1) 和 F(n-2)。这个递推关系是解决问题的关键。

思路选择

动态规划（空间优化） 是解决此问题的标准最优思路。

• 状态转移方程为：dp[i] = dp[i-1] + dp[i-2]。

• 我们可以发现，计算当前项只需要前两项的值。因此，没有必要创建一个完整的 dp 数组来存储所有中间结果。

• 只需使用两个变量来“滚动”记录前两个状态的值，就可以在常数空间内完成计算。

关键步骤

1. 处理边界情况：如果 n < 2，根据定义直接返回 n。

2. 初始化：初始化两个变量 a = 0 (代表 F(i-2)) 和 b = 1 (代表 F(i-1))。

3. 循环迭代：从 i = 2 开始循环到 n。 a. 在循环中，计算当前项的值 sum = a + b。 b. 更新状态以备下次循环：a 更新为原来的 b，b 更新为 sum。

4. 返回结果：循环结束后，b 变量中存储的就是 F(n) 的值，返回即可。

代码实现

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
    if (n < 2) return n;

    // a 代表 F(i-2), b 代表 F(i-1)
    let a = 0, b = 1;

    for (let i = 2; i <= n; i++) {
        // 计算 F(i)
        const sum = a + b;
        // 滚动更新
        a = b;
        b = sum;
    }

    return b;
};

复杂度分析

• 时间复杂度：O(n) 我们只需要一个从 2 到 n 的循环，循环次数与 n 成正比。

• 空间复杂度：O(1) 我们只使用了常数个额外变量，空间消耗与输入 n 的大小无关。

相关题目

• 0070.爬楼梯

• LCR 126.斐波那契数

• LCR 127.训练计划 V

总结

本题是动态规划最基础的模型之一。通过识别出问题的斐波那契数列本质，并利用“滚动数组”的思想进行空间优化，可以得到一个非常高效的解决方案。这是所有动态规划问题学习的起点。