1137. N-th Tribonacci Number

Description

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

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.

Python3JavaC++GoTypeScriptJavaScriptPHP

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

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;
    }
};

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 {
    let [a, b, c] = [0, 1, 1];
    while (n--) {
        let d = a + b + c;
        a = b;
        b = c;
        c = d;
    }
    return a;
}

/**
 * @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) {
        $a = 0;
        $b = 1;
        $c = 1;

        while ($n--) {
            $d = $a + $b + $c;
            $a = $b;
            $b = $c;
            $c = $d;
        }

        return $a;
    }
}

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)\).