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

Categories:

题目描述
思路分析
1. 解法一：空间优化动态规划（推荐）
2. 解法二：线性动态规划
相似题目

题目描述

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

思路分析

解法一：空间优化动态规划（推荐）

核心思路：斐波那契数列满足 F(n) = F(n-1) + F(n-2)，是经典的线性 DP 问题。

状态定义：F(n) 表示第 n 个斐波那契数

转移方程：F(n) = (F(n-1) + F(n-2)) % 1000000007

取模操作：每次加法后立即取模，防止大数溢出

空间优化：只需保留前两个值 pre、cur，滚动更新即可将空间压缩至 O(1)

复杂度分析：

时间复杂度：O(n)，其中 n 为输入参数，需线性遍历一次

空间复杂度：O(1)，仅使用常数级变量

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int pre = 0, cur = 1;
        // 从第 2 项开始滚动更新，每步取模防止溢出
        for (int i = 2; i <= n; i++) {
            int next = (pre + cur) % 1_000_000_007;
            pre = cur;
            cur = next;
        }
        return cur;
    }
}

func fib(n int) int {
    if n < 2 {
        return n
    }
    pre, cur := 0, 1
    // 从第 2 项开始滚动更新，每步取模防止溢出
    for i := 2; i <= n; i++ {
        pre, cur = cur, (pre+cur)%1_000_000_007
    }
    return cur
}

解法二：线性动态规划

核心思路：使用数组显式存储所有子问题的解，便于理解状态转移的全过程。

状态定义：dp[i] 表示第 i 个斐波那契数

转移方程：dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

初始值：dp[0] = 0，dp[1] = 1

复杂度分析：

时间复杂度：O(n)，其中 n 为输入参数，需线性遍历一次

空间复杂度：O(n)，其中 n 为输入参数，需要大小为 n+1 的 dp 数组

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        // 自底向上填表，每步取模防止溢出
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1_000_000_007;
        }
        return dp[n];
    }
}

func fib(n int) int {
    if n < 2 {
        return n
    }
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    // 自底向上填表，每步取模防止溢出
    for i := 2; i <= n; i++ {
        dp[i] = (dp[i-1] + dp[i-2]) % 1_000_000_007
    }
    return dp[n]
}

相似题目

题目	难度	考察点
509. 斐波那契数	简单	动态规划 / 记忆化递归
70. 爬楼梯	简单	动态规划 / 斐波那契变形
746. 使用最小花费爬楼梯	简单	动态规划 / 费用最优
198. 打家劫舍	中等	动态规划 / 线性 DP
213. 打家劫舍 II	中等	动态规划 / 环形 DP
1137. 第 N 个泰波那契数	简单	动态规划 / 滚动数组
剑指 Offer 10- II. 青蛙跳台阶问题	简单	动态规划 / 斐波那契变形

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/93287447