# 1137. N-th Tribonacci Number

## Description

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4


Example 2:

Input: n = 25
Output: 1389537


Constraints:

• 0 <= n <= 37
• The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

## Solutions

Solution 1: Dynamic Programming

According to the recurrence relation given in the problem, we can use dynamic programming to solve it.

We define three variables $a$, $b$, $c$ to represent $T_{n-3}$, $T_{n-2}$, $T_{n-1}$, respectively, with initial values of $0$, $1$, $1$.

Then we decrease $n$ to $0$, updating the values of $a$, $b$, $c$ each time, until $n$ is $0$, at which point the answer is $a$.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the given integer.

Solution 2: Matrix Exponentiation to Accelerate Recurrence

We define $Tib(n)$ as a $1 \times 3$ matrix $\begin{bmatrix} T_n & T_{n - 1} & T_{n - 2} \end{bmatrix}$, where $T_n$, $T_{n - 1}$ and $T_{n - 2}$ represent the $n$th, $(n - 1)$th and $(n - 2)$th Tribonacci numbers, respectively.

We hope to derive $Tib(n)$ from $Tib(n-1) = \begin{bmatrix} T_{n - 1} & T_{n - 2} & T_{n - 3} \end{bmatrix}$. That is, we need a matrix $base$ such that $Tib(n - 1) \times base = Tib(n)$, i.e.,

$\begin{bmatrix} T_{n - 1} & T_{n - 2} & T_{n - 3} \end{bmatrix} \times base = \begin{bmatrix} T_n & T_{n - 1} & T_{n - 2} \end{bmatrix}$

Since $T_n = T_{n - 1} + T_{n - 2} + T_{n - 3}$, the matrix $base$ is:

$\begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}$

We define the initial matrix $res = \begin{bmatrix} 1 & 1 & 0 \end{bmatrix}$, then $T_n$ is equal to the sum of all elements in the result matrix of $res$ multiplied by $base^{n - 3}$. This can be solved using matrix exponentiation.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$.

• class Solution {
public int tribonacci(int n) {
int a = 0, b = 1, c = 1;
while (n-- > 0) {
int d = a + b + c;
a = b;
b = c;
c = d;
}
return a;
}
}

• class Solution {
public:
int tribonacci(int n) {
long long a = 0, b = 1, c = 1;
while (n--) {
long long d = a + b + c;
a = b;
b = c;
c = d;
}
return (int) a;
}
};

• class Solution:
def tribonacci(self, n: int) -> int:
a, b, c = 0, 1, 1
for _ in range(n):
a, b, c = b, c, a + b + c
return a


• func tribonacci(n int) int {
a, b, c := 0, 1, 1
for i := 0; i < n; i++ {
a, b, c = b, c, a+b+c
}
return a
}

• function tribonacci(n: number): number {
if (n === 0) {
return 0;
}
if (n < 3) {
return 1;
}
const a = [
[1, 1, 0],
[1, 0, 1],
[1, 0, 0],
];
return pow(a, n - 3)[0].reduce((a, b) => a + b);
}

function mul(a: number[][], b: number[][]): number[][] {
const [m, n] = [a.length, b[0].length];
const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
for (let k = 0; k < b.length; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}

function pow(a: number[][], n: number): number[][] {
let res = [[1, 1, 0]];
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}


• /**
* @param {number} n
* @return {number}
*/
var tribonacci = function (n) {
let a = 0;
let b = 1;
let c = 1;
while (n--) {
let d = a + b + c;
a = b;
b = c;
c = d;
}
return a;
};


• class Solution {
/**
* @param Integer $n * @return Integer */ function tribonacci($n) {
if ($n == 0) { return 0; } elseif ($n == 1 || $n == 2) { return 1; }$dp = [0, 1, 1];
for ($i = 3;$i <= $n;$i++) {
$dp[$i] = $dp[$i - 1] + $dp[$i - 2] + $dp[$i - 3];
}
return $dp[$n];
}
}