LeetCode 1137. 第 N 个泰波那契数

约 4 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 简单 LeetCode 75
标签
动态规划 数学 记忆化

题目描述

✅ 1137. 第 N 个泰波那契数

image-20260928233922906

题意分析

泰波那契序列给定三项初值：T0 = 0、T1 = 1、T2 = 1。从第三项开始，每一项都等于紧挨着它的前三项之和，要求返回下标为 n 的那一项。

下标从零开始，不是求前 n 项的总和。题目中 n 不超过三十七，保证答案能放入 32 位整数，不需要取模；n 落在前三个下标时直接返回对应初值。

解法：保留最近三项滚动递推

核心思路

[!blue]

从已知初值向前递推，每一项只需要计算一次。若直接按定义递归求前三项，同一个较小下标会在不同分支中被反复求值；顺序计算就能复用已经得到的结果。

求当前 Ti 时，只会读取 T(i - 3)、T(i - 2)、T(i - 1)，更早的项不会再直接参与之后的转移。因此用 t0、t1、t2 保存这三个相邻状态就足够，不必保存整个数组。

每轮先用三个旧值求出 cur，再把窗口移动为旧 t1、旧 t2、cur。更新后它们正好对应下一轮需要的前三项。Java 按从旧到新的顺序赋值，Go 的多重赋值先计算右侧，都能避免提前覆盖仍要读取的旧状态。

初始三个变量对应下标零、一、二，所以循环从 i = 3 开始并且包含 n。最后一轮结束后，最新的 t2 就是 Tn；前三项提前返回，也避免把初值误当成已经执行过转移的状态。

解题步骤

  1. n < 3 时，零返回零，一或二返回一。
  2. 初始化三个滚动变量为 0、1、1。
  3. 从下标三计算到 n，先把三个旧值相加，再将它们整体向下一项平移。
  4. 返回最后一个滚动变量 t2。

代码实现

class Solution {
    public int tribonacci(int n) {
        if (n < 3) {
            // T0 = 0，T1 = T2 = 1，三项都是题目给定的初值。
            return n == 0 ? 0 : 1;
        }

        int t0 = 0;
        int t1 = 1;
        int t2 = 1;

        for (int i = 3; i <= n; i++) {
            // 进入本轮时 t0、t1、t2 分别是 T(i-3)、T(i-2)、T(i-1)。
            int cur = t0 + t1 + t2;

            // 平移窗口时先搬最旧的一项，避免读到被覆盖的新值。
            t0 = t1;
            t1 = t2;
            t2 = cur;
        }

        return t2;
    }
}

func tribonacci(n int) int {
    if n < 3 {
        // T0 = 0，T1 = T2 = 1，三项都是题目给定的初值。
        if n == 0 {
            return 0
        }
        return 1
    }

    t0, t1, t2 := 0, 1, 1
    for i := 3; i <= n; i++ {
        // 进入本轮时 t0、t1、t2 分别是 T(i-3)、T(i-2)、T(i-1)。
        cur := t0 + t1 + t2
        // 多重赋值先算完右侧再统一写入，天然不存在覆盖顺序问题。
        t0, t1, t2 = t1, t2, cur
    }
    return t2
}

复杂度分析

  • 时间复杂度：$O(n + 1)$，初值为常数处理，其余下标各进行一次加法转移。
  • 空间复杂度：$O(1)$，仅保存三个历史值和本轮结果。

关键点总结

[!green]

  • 三个变量的含义是当前项之前的连续三项，初始下标与循环起点必须对应。
  • 只依赖有限个相邻状态，可以滚动覆盖已经不再需要的最旧项。
  • 先计算本轮新值，再移动窗口，保持计算使用的是同一轮旧状态。

易错点总结

[!yellow]

  • 初值区间直接返回 n，会把下标二的答案错误写成二。
  • 循环不包含 n，得到的是目标的前一项。
  • 覆盖某个变量后才计算三项之和，会重复使用新值并丢失旧项。
  • 只加前两项或套用其他递推初值，改变了泰波那契序列的定义。
  • 自行添加取模会改变题目要求的精确整数结果。

相似题目

题目 难度 关联与区别
509. 斐波那契数 简单 同样由固定数量的最近状态递推，斐波那契只依赖两项，本题依赖三项。
70. 爬楼梯 简单 同样可以把线性DP压缩为滚动变量，但初值与递推项数需按各自题意确定。
91. 解码方法 中等 按最后一段长度递推前缀方案数；本题依赖前三个状态，该题最后编码可占一位或两位。
746. 使用最小花费爬楼梯 简单 按最后一段长度递推前缀方案数；本题依赖前三个状态，该题转为达到当前台阶的最小费用。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/60105109
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！