LCR 126.斐波那契数

难度：🟢 简单

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

链接：LCR 126. 斐波那契数 (剑指 Offer 10- I. 斐波那契数列)

题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(n)）。斐波那契数列的定义如下：

• F(0) = 0, F(1) = 1

• F(n) = F(n - 1) + F(n - 2), 其中 n > 1

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1000000007（1e9+7），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

解题思路

核心思想

本题是求解斐波那契数列的第 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) % 1000000007，注意要进行取模运算。 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;
    const MOD = 1000000007;

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

    return b;
};

复杂度分析

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

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

相关题目

• 0070.爬楼梯

• 0198.打家劫舍

• LCR 127.训练计划 V

总结

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