题目描述

Tribonacci 序列 $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，返回 $T_n$ 的值。

样例

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

输入：n = 25
输出：1389537

限制

• 0 <= n <= 37
• 答案保证在 32 位整数内，即 answer <= 2^31 - 1。

算法

(模拟) $O(n)$

1. 设立三个变量 a，b 和 c 表示 $T_{i-3}, T_{i-2}, T_{i-1}$。
2. 每次更新 $T_i = a + b + c$，i 往后移动，然后依次更新 a， b 和 c。

时间复杂度

• 循环一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅定义常数个变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0)
            return 0;
        else if (n == 1)
            return 1;
        else if (n == 2)
            return 1;

        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int t = a + b + c;
            a = b;
            b = c;
            c = t;
        }
        return c;
    }
};