LC1137. 第 N 个泰波那契数

题目描述

泰波那契序列 T(n) 定义如下： T(0) = 0, T(1) = 1, T(2) = 1, 且在 n >= 0 的条件下 T(n+3) = T(n) + T(n+1) + T(n+2) 给你整数 n，请返回第 n 个泰波那契数 T(n )的值。

示例 1： 输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2： 输入：n = 25 输出：1389537

提示： 0 <= n <= 37 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

题目解析

题目在说什么

这道题让我们计算一个叫“泰波那契数”的东西。它和著名的“斐波那契数”很像，但规则稍微复杂一点。 斐波那契数是前两个数相加得到下一个数：比如 0, 1, 1, 2, 3, 5... 而泰波那契数是 前三个数相加 得到下一个数。题目给了我们开头三个数：

• T(0) = 0
• T(1) = 1
• T(2) = 1

然后对于 n >= 0，有公式： T(n+3) = T(n) + T(n+1) + T(n+2)

换句话说，从第3个数开始，每个数都是它前面三个数的和。 比如：

• T(3) = T(0) + T(1) + T(2) = 0 + 1 + 1 = 2
• T(4) = T(1) + T(2) + T(3) = 1 + 1 + 2 = 4

题目会给你一个 n（0 到 37 之间），你要返回 T(n) 的值。

---

思路是怎么来的

想象你在玩一个“数字接力”游戏： 你手上有三个数字，比如一开始是 0、1、1。 你要不断算出下一个数字，然后扔掉最前面的那个，把新数字加到最后面，保持手里始终只有三个数字。

比如：

• 手里：0, 1, 1 → 算出下一个：0+1+1=2 → 扔掉0，变成：1, 1, 2
• 手里：1, 1, 2 → 算出下一个：1+1+2=4 → 扔掉1，变成：1, 2, 4
• 手里：1, 2, 4 → 算出下一个：1+2+4=7 → 扔掉1，变成：2, 4, 7

这样一直算到第 n 个，你就能得到答案。

这个思路非常直接：我们不需要记住所有历史数字，只需要记住最近三个，然后不断滚动更新。 就像排队时，你只需要知道前面三个人是谁，就能算出下一个是谁，然后前面的人就可以走了。

---

代码逐步拆解

我们来看参考代码，一行一行讲清楚。

class Solution {
    public int tribonacci(int n) {

• 定义一个方法，名字叫 tribonacci，参数是 n，返回一个整数。

        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }

• 如果 n 是 0，直接返回 0，因为题目说了 T(0)=0。
• 如果 n 是 1 或 2，直接返回 1，因为 T(1)=1, T(2)=1。
• 这是处理最简单的情况，就像你问“第0个是什么？”答案就是0，不需要计算。

        int p = 0, q = 1, r = 1;
        int s = 0;

• 我们定义三个变量 p, q, r，分别代表“当前三个数”中的第一个、第二个、第三个。

一开始 p=0（T(0)），q=1（T(1)），r=1（T(2)）。

• s 用来存放我们算出来的下一个数，先初始化为0。

        for (int i = 3; i <= n; i++) {

• 从 i=3 开始循环，一直算到 i=n 为止。
• 为什么从3开始？因为前三个数我们已经知道了，不需要算。
• 每循环一次，我们就计算一个“下一个数”。

            s = p + q + r;

• 把当前三个数加起来，得到下一个数，存到 s 里。
• 比如第一次循环：s = 0 + 1 + 1 = 2，这就是 T(3)。

            p = q;
            q = r;
            r = s;

• 然后我们要“滚动”一下：
• 把原来的第二个数 q 变成新的第一个数 p