LeetCode 1137. 第 N 个泰波那契数

2026-07-14 HGNULB 约 9 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 1137. 第 N 个泰波那契数

题意分析

题目给定一个泰波那契序列：T0 = 0、T1 = 1、T2 = 1，从第四项开始，每一项等于紧挨在它前面的三项之和，写成递推式就是 Tn+3 = Tn + Tn+1 + Tn+2（n >= 0）。输入一个整数 n，要求返回 Tn 这一个值，而不是整条序列。

约束是 0 <= n <= 37，并且题面明确保证答案落在 32 位整数内（answer <= 2^31 - 1）。这两句话透露了两个信号：一是 n 极小，老老实实按定义从前往后逐项求值的代价完全可以接受，不需要任何数学变换；二是既不用取模也不会溢出，int 就够用 —— T37 = 2082876103，已经贴着 2^31 - 1 = 2147483647 的上限，可见 37 这个上界正是为了卡住 int 而设的。

需要格外小心的边界是最前面三项，它们是题目直接给定的初值，不能反过来用递推式算出来：n = 0 时答案是 0，n = 1 时答案是 1，n = 2 时答案也是 1。注意 T1 和 T2 相等，这一点和斐波那契不同 —— 斐波那契只给两个初值，它的第三项是算出来的，而这里第三项是白送的。第一个真正需要计算的是 n = 3：T3 = T0 + T1 + T2 = 0 + 1 + 1 = 2；接着 T4 = T1 + T2 + T3 = 1 + 1 + 2 = 4，与官方样例 n = 4 → 4 吻合。另一个官方样例是 n = 25 → 1389537。

解法：滚动变量递推

核心思路

递推式最直白的翻译是自顶向下的递归：要 T(n) 就去要 T(n-1)、T(n-2)、T(n-3)。但这样每一项会被反复重算 —— 调用次数满足 C(n) = 1 + C(n-1) + C(n-2) + C(n-3)，在 n = 37 时高达 4047854365 次（约 40 亿次），根本跑不完。问题不在递推式本身，而在求值顺序：自顶向下会让同一个子问题被不同的父问题反复触发。

第一层修正是记忆化：给每个 T(k) 配一个缓存格子，算过就直接取。重复子问题被消掉之后每一项只算一次，时间降到 $O(n)$，但代价是要额外背一个长度为 n + 1 的缓存和一条深度为 n 的递归链。

第二层观察才是关键：T(k) 只依赖 T(k-1)、T(k-2)、T(k-3) 三项，回看距离最远就是 3。也就是说，一旦 T(k) 算完，T(k-3) 就再也不会被任何后续项引用了。缓存里绝大多数格子在被写入之后立刻变成死数据，真正活着的永远只有一个宽度为 3 的窗口。既然如此，就把整个缓存换成三个变量，并把求值顺序反转成自底向上：从已知的三个初值出发，每算出一项就把窗口向右平移一格。

正确性由一条不变量保证：循环变量 i 每轮开始时，t0 = T(i-3)、t1 = T(i-2)、t2 = T(i-1)。进入循环前 i = 3，此时 t0 = T0 = 0、t1 = T1 = 1、t2 = T2 = 1，不变量成立；每一轮先用三者求和得到 T(i)，再把 (t0, t1, t2) 整体替换成 (t1, t2, T(i))，也就是 (T(i-2), T(i-1), T(i))，恰好是下一轮 i + 1 所需的三项，不变量得以保持。循环在 i 走过 n 之后结束，最后一轮已把 T(n) 写进 t2，所以返回 t2 就是答案。

自底向上还顺带解决了递归的另一个隐患：没有函数调用栈，空间从 $O(n)$ 压到 $O(1)$。至于 n < 3，它落在初值区间内，窗口还没开始平移，不变量的前置条件也不成立，只能按定义单独返回。

解题步骤

先单独处理 n < 3：因为这三项是题目给定的初值而非算出来的，而循环的不变量要求窗口里已经装满三个确定值，所以初值区间不能进循环。n = 0 返回 0，n = 1 和 n = 2 都返回 1。

初始化 t0 = 0、t1 = 1、t2 = 1：为的是让 i = 3 这一轮开始时不变量 t0 = T(i-3)、t1 = T(i-2)、t2 = T(i-1) 成立。

让 i 从 3 递增到 n，上界取闭区间：每一轮负责算出恰好一项，第一个待算的是 T3，最后一个是 T(n)，写成 i <= n 才能把 T(n) 算出来。

每轮先求 cur = t0 + t1 + t2：此刻三个变量正好是 T(i) 依赖的三项，必须在任何变量被改写之前把这个和取出来。

再按 t0 ← t1、t1 ← t2、t2 ← cur 的顺序平移窗口：从最旧的一项开始搬，每个变量在被覆盖之前它的旧值已经被读走了；顺序一旦反过来就会读到刚写进去的新值。

循环结束后返回 t2：最后一轮 i = n 把 T(n) 写进了 t2，它就是答案。

以 n = 6 走一遍：进入循环前 (t0, t1, t2) = (0, 1, 1)，分别代表 T0、T1、T2。i = 3：cur = 0 + 1 + 1 = 2，平移后 (1, 1, 2)。i = 4：cur = 1 + 1 + 2 = 4，平移后 (1, 2, 4)。i = 5：cur = 1 + 2 + 4 = 7，平移后 (2, 4, 7)。i = 6：cur = 2 + 4 + 7 = 13，平移后 (4, 7, 13)。循环结束，返回 t2 = 13，即 T6 = 13。顺着中间几轮的 cur 还能读出 T3 = 2、T4 = 4、T5 = 7，其中 T4 = 4 与官方样例一致。若输入是 n = 2，则连循环都不会进入，在第一步就直接返回 1；这正是把 n < 3 单独拎出来的原因 —— 否则 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)$，n < 3 时直接返回；否则循环从 i = 3 执行到 i = n，共 n - 2 轮，每轮只做两次加法和常数次赋值，都是常数代价。

空间复杂度：$O(1)$，全程只用 t0、t1、t2、cur 四个整型变量，与 n 无关；既没有缓存数组，也没有递归调用栈。

关键点总结

递推式描述的是数学关系，不等于实现方式。同一条 T(n) = T(n-1) + T(n-2) + T(n-3)，自顶向下展开会因重复子问题退化成指数级，自底向上求值就是线性的 —— 遇到指数级递归，先想能不能反转求值顺序，而不是先想怎么剪枝。

记忆化消掉的是重复计算，滚动变量还能顺手把存储也消掉。判据是回看距离：当一个状态只依赖最近固定宽度的若干项时，缓存里超出这个宽度的部分永远不会再被读取，可以整段丢弃，滚动窗口的宽度就等于递推式里回看的最大距离。

写滚动更新之前先把不变量讲清楚（每轮开始时每个变量代表哪一项）。一旦不变量定下来，初始化的值、赋值的顺序、循环的边界都能由它直接推出来，而不必靠改一改试一试。

用顺序赋值实现窗口平移时，永远从最旧的一项开始搬；或者先用临时变量把新值算好，再整体替换。像 Go 的多重赋值 t0, t1, t2 = t1, t2, cur 会先把右侧全部求值完再统一写入，从语言层面免掉了这类顺序陷阱。

题目给定的初值和递推算出来的项必须分开对待。初值区间要在循环外单独返回，否则循环的前置条件不成立，出口变量的语义也会对不上。

数据范围是出题人给的设计提示。0 <= n <= 37 加上「答案落在 32 位整数内」，等于同时告诉你三件事：线性扫一遍就够快，不必去追矩阵快速幂之类的对数级做法；不需要取模；也不需要比 int 更宽的整型。

易错点总结

三个初值记错，把 T2 当成需要算出来的项：照搬斐波那契的两个初值再补一个 0，写成 t0 = 0, t1 = 1, t2 = 0 → n = 3 返回 1（应为 2），n = 4 返回 2（应为 4），n = 25 返回 634061（应为 1389537）。

初值写成 0, 1, 2：以为第三项还要在 0 + 1 + 1 的基础上再累一次 → n = 3 返回 3、n = 4 返回 6、n = 25 返回 2145013，从第一项算起就整体偏大。

滚动赋值顺序写反：先写 t1 = t2 再写 t0 = t1，t0 拿到的是刚被覆盖的新 t1 → n = 3 返回 2、n = 4 返回 4，恰好都对（因为 T1 = T2 = 1 把错误掩盖了），但 n = 5 返回 8（应为 7），n = 25 返回 8388608（应为 1389537）。小样例全过、提交才挂，是这道题最阴的一条。

不用临时变量就地滚动：写成 t0 = t1; t1 = t2; t2 = t0 + t1 + t2;，求和时读到的已经是平移之后的值 → n = 3 返回 3（应为 2），n = 4 返回 7（应为 4），n = 25 返回 768398401。

n < 3 照抄斐波那契的 return n：斐波那契里 n < 2 时 return n 是对的，但这里 T2 = 1 不等于 2 → n = 2 返回 2（应为 1），而 n = 0、n = 1、n = 4、n = 25 全都正确，只有唯一一个用例会暴露，极容易漏测。

循环上界写成 i < n：最后一项没算 → n = 3 返回 1（即 T2），n = 4 返回 2，n = 5 返回 4，n = 25 返回 755476，整个答案前移了一位。

循环结束后返回错的变量：把 return t2 写成 return t0 → n = 4 返回 1，n = 5 返回 2，n = 25 返回 410744，相当于把答案退回了两项。

直接照着递推式写不带记忆化的递归：调用次数满足 C(n) = 1 + C(n-1) + C(n-2) + C(n-3)，n = 25 时是 2700421 次还能勉强跑过，n = 37 时就涨到 4047854365 次（约 40 亿次），提交会超时。

改用记忆化递归时缓存数组只开 n 而不是 n + 1：n 本身也要占一个格子 → 访问 memo[n] 越界，Java 抛 ArrayIndexOutOfBoundsException，Go 触发 index out of range 的 panic，n = 3 这种最小的非初值用例就会直接崩。

看到「序列求值」就上矩阵快速幂：n 最大只有 37，线性递推总共不到 40 次加法，换成 $O(\log n)$ 的矩阵幂既没有实际收益，又要多写一套 3 阶矩阵乘法，出错面反而变大 —— 复杂度更优不等于这道题更该用它。

相似题目

题目	难度	考察点
509. 斐波那契数	简单	回看距离只有 2，窗口少一个变量，且第三项是算出来的而非题目给定
70. 爬楼梯	简单	递推式要自己从「最后一步走 1 阶还是 2 阶」推出来，不是题面直给
面试题 08.01. 三步问题	简单	同样回看三项，但答案会溢出，每一步都得对 1e9+7 取模
746. 使用最小花费爬楼梯	简单	转移带 `min` 决策而非纯求和，窗口里存的是最优值不是序列值
91. 解码方法	中等	两个转移项是否可用取决于当前字符，得先做合法性判断再累加
LCR 091. 粉刷房子	中等	每一层有多个并列状态，滚动的是一整组状态而不是单个数值