LeetCode 剑指 Offer 10- I. 斐波那契数列

约 4 分钟
文章信息 17 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 剑指 Offer 剑指 Offer（第 2 版） 腾讯 字节 阿里 美团 百度 网易 快手 滴滴 虾皮
标签
动态规划 数学 记忆化搜索

题目描述

✅ 剑指 Offer 10- I. 斐波那契数列

image-20261001224841784

image-20260928203104353

image-20260928203104354

题意分析

斐波那契数列从第零项开始，定义 F(0) = 0、F(1) = 1，之后每一项等于前两项之和。给定 n，返回 F(n) 对 1000000007 取模后的结果，而不是返回前 n 项或这些项的总和。

题目允许 n = 0，此时答案为零。真实的斐波那契数会很快超过普通整数范围，因此计算过程也需要取模，不能等完整求出第 n 项后才处理溢出问题。

解法：滚动变量递推

核心思路

[!blue]

递推式已经说明下一项只依赖前两项。自底向上按顺序计算时，更早的项以后不会再被直接使用，因此只需两个变量保存相邻两项，无需建立整个数组，也无需展开存在大量重复子问题的朴素递归。

规定第 i 轮开始时，a 保存 F(i) 的余数，b 保存 F(i + 1) 的余数。初始化 a = 0、b = 1，对应 i = 0。先计算 sum = (a + b) % MOD，得到下一项 F(i + 2) 的余数，再让 a = b、b = sum，就把两个状态向前推进一项。

逐步取模不会改变最终余数，因为加法满足 (x + y) mod MOD = ((x mod MOD) + (y mod MOD)) mod MOD。每轮结束后两个变量都小于 MOD，下一次相加最多为 2 * (MOD - 1)，在本题中仍小于 32 位有符号整数上限，所以代码的整数加法安全。

更新必须同时基于旧的两项。Java 先用临时变量保存和，再覆盖 a、b；Go 的多重赋值会先计算全部右侧表达式，可以直接写 a, b = b, (a + b) % mod。

经过 n 轮，轮次不变量变为 a = F(n) mod MOD，因此返回 a。n = 0 时不执行循环，初始化值已经是答案，不需要另写特判。

解题步骤

  1. 初始化 a = 0、b = 1 和模数。
  2. 重复 n 次，用旧 a、旧 b 求出下一项的余数。
  3. 将相邻两项更新为旧 b 和新余数。
  4. 返回 a，它对应第 n 项。

代码实现

class Solution {
    private static final int MOD = 1000000007;

    public int fib(int n) {
        int a = 0;
        int b = 1;

        for (int i = 0; i < n; i++) {
            // 先用两个旧项计算新项，再整体向前推进，循环后 a 是目标项。
            int sum = (a + b) % MOD;

            a = b;
            b = sum;
        }

        return a;
    }
}

func fib(n int) int {
    const mod = 1000000007
    a, b := 0, 1
    for i := 0; i < n; i++ {
        // 同时读取两个旧项再推进，循环后 a 是目标项。
        a, b = b, (a+b)%mod
    }
    return a
}

复杂度分析

  • 时间复杂度：$O(n)$，推进 n 轮，每轮只有固定次数的整数运算。
  • 空间复杂度：$O(1)$，只保存两个相邻状态及一个临时和。

关键点总结

[!green]

  • 两个变量保存的下标必须明确：每轮开始为第 i、i + 1 项，循环结束返回第 n 项。
  • 加法可以逐步取模，既保持最终余数正确，也限制中间数值范围。
  • 先读取旧状态再覆盖，滚动递推才能等价于原递推式。

易错点总结

[!yellow]

  • 只在最后取模，中间的真实数值可能已经溢出，之后取模无法补救。
  • 将初值改成两个一，会变成另一组初始条件，整个结果序列发生偏移。
  • Java 先执行 a = b 再用 a + b 求下一项，会丢失旧 a，错误地把旧 b 加两次。
  • 循环轮数和返回变量不配套，会返回相邻的另一项；本实现执行 n 轮后返回 a。
  • 取模后的数值不再保持真实斐波那契数的大小关系，不能凭它是否增大来提前终止递推。

相似题目

题目 难度 关联与区别
70. 爬楼梯 简单 递推关系相近但初值不同，不能因为都依赖前两项就直接共用返回值。
1137. 第 N 个泰波那契数 简单 把依赖前两项扩展为前三项，滚动变量的数量随依赖宽度变化。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/93287447
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！