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

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

题目描述

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

image-20250510211957880

image-20250510212014931

题意分析

题目给出一个整数 n，要求返回斐波那契数列的第 n 项。数列本身由题面直接定义：F(0) = 0，F(1) = 1，此后每一项等于前面两项之和。也就是说，输入是一个下标，输出是一个确定的数值，中间没有任何选择或搜索的成分。

真正需要注意的约束有两条。第一条是初值：本题的起点是「0 和 1」，不是「1 和 1」。剑指 Offer 里紧挨着的青蛙跳台阶问题从 1, 1 起步，两题的递推式完全一样，只有初值不同，混淆初值会让所有答案整体错位一项。

第二条是取模：题面明确要求「答案需要取模 1e9+7（1000000007）」，因为 n 可以取到 100，而 F(100) 早已远远超出 32 位甚至 64 位整数的范围。取模不是可选的收尾动作，而是题目对返回值的定义本身。

边界方面只有两个小输入需要单独确认：n = 0 要返回 0，n = 1 要返回 1。这两项由定义直接给出，不参与任何推导。

解法：滚动变量递推

核心思路

问题关键：直接递归虽然符合定义，但同一个 F(i) 会被重复计算，时间复杂度接近 $O(2^n)$。真正需要的状态只有 F(0) 到 F(n)，应改为从小到大递推。

为什么选滚动变量：F(i + 2) = F(i) + F(i + 1) 只依赖相邻两项，完整 DP 数组没有必要。用 a、b 保存窗口即可把空间降到 $O(1)$。

不变量：第 i 轮开始前，a = F(i) mod MOD，b = F(i + 1) mod MOD。本轮先计算 sum = (a + b) mod MOD，再更新为 a = b、b = sum，因此下一轮仍满足不变量。执行 n 轮后，a = F(n) mod MOD，直接返回 a。

正确性：初始 a = F(0) = 0、b = F(1) = 1，不变量成立；每轮严格应用斐波那契递推式，所以由数学归纳法可知最终结果正确。加法满足模运算封闭性，每步取模与最后取模等价，同时避免中间值溢出。

解题步骤

面试时可按下面 4 步口述：

  1. 初始化 a = 0、b = 1，分别表示当前相邻的两项。
  2. 循环 n 次，计算 sum = (a + b) % MOD。
  3. 将窗口右移为 a = b、b = sum。
  4. 循环结束后 a 正好移动到 F(n)，返回 a。

例如 n = 5，(a,b) 依次为 (0,1) -> (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,8)，返回 5。n = 0 时循环不执行，自然返回 0。

代码实现

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++) {
            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, b = b, (a+b)%mod
    }
    return a
}

复杂度分析

  • 时间复杂度：$O(n)$。循环执行 n 次，每次只做常数次运算。
  • 空间复杂度：$O(1)$。只维护两个状态和一个临时结果。

关键点总结

  • 朴素递归慢在重复计算，不是递推式本身复杂。
  • 只依赖前两项时，用滚动变量即可，无需 DP 数组。
  • 用 a = F(i) 定义循环不变量，可以自然覆盖 n = 0，省去边界分支。
  • 取模必须放在每次加法中；取模后的数值不再保持原数列的大小关系。

易错点总结

  • 只在最后取模会让中间结果先溢出；Java 的 int 在 F(47) 已无法保存真值。
  • 初值应为 (0,1)。若照搬青蛙跳台阶的 (1,1)，整个序列会错一位。
  • 滚动更新必须保留旧的 a、b。Java 需要先算 sum；Go 的多重赋值会先计算右侧，可直接更新。
  • 循环执行 n 轮后返回 a；若采用“从第 2 项递推”的模板，则循环边界和返回变量必须同步调整。

相似题目

题目 难度 考察点
70. 爬楼梯 简单 同一递推式的计数版本，初值改为 1, 1，答案整体右移一项
509. 斐波那契数 简单 本题去掉取模要求的版本，可直接用 int 返回真值
746. 使用最小花费爬楼梯 简单 转移从求和变为取 min 并叠加代价，两状态滚动不变
LCR 088. 使用最小花费爬楼梯 简单 746 的同题换皮，用来检验滚动写法的边界是否记牢
剑指 Offer 10- II. 青蛙跳台阶问题 简单 递推式与取模完全相同，唯一区别是初值为 1, 1
面试题 08.01. 三步问题 简单 依赖窗口扩到 3 项，滚动变量随之从两个变成三个