How to Compute the N-th Tribonacci Number using Iterative Dynamic Programming Algorithm?

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.

A Tribonacci is very much similar to Fibonacci except that the Tribonacci is the sum of its previous 3 Tribonacci in the sequences.

Iterative Approach to compute the n-th Tribonacci

Like the Fibonacci, we can use three variables to iterate the process, at each iteration, we need to shift those three variables i.e. T(i), T(i+1) and T(i+2) respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int tribonacci(int n) {
        int t[3] = {0, 1, 1};
        if (n <= 2) return t[n];
        for (int i = 3; i <= n; ++ i) {
            int a = t[0] + t[1] + t[2];
            t[0] = t[1];
            t[1] = t[2];
            t[2] = a;
        }
        return t[2];
    }
};

class Solution {
public:
    int tribonacci(int n) {
        int t[3] = {0, 1, 1};
        if (n <= 2) return t[n];
        for (int i = 3; i <= n; ++ i) {
            int a = t[0] + t[1] + t[2];
            t[0] = t[1];
            t[1] = t[2];
            t[2] = a;
        }
        return t[2];
    }
};

The final answer is at T[2] – where it is the last Tribonacci number computed. The above takes O(N) time and O(1) constant space.

Dynamic Programming Algorithm to compute the n-th Tribonacci number

The Dynamic programming equation is actually already given already, thus we just have to implement it and store the intermediate values in the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int tribonacci(int n) {
        vector<int> f(max(3, n + 1));
        f[0] = 0;
        f[1] = 1;
        f[2] = 1;
        if (n <= 2) return f[n];
        for (int i = 3; i <= n; ++ i) {
            f[i] = f[i - 1] + f[i - 2] + f[i - 3];
        }
        return f[n];
    }
};

class Solution {
public:
    int tribonacci(int n) {
        vector<int> f(max(3, n + 1));
        f[0] = 0;
        f[1] = 1;
        f[2] = 1;
        if (n <= 2) return f[n];
        for (int i = 3; i <= n; ++ i) {
            f[i] = f[i - 1] + f[i - 2] + f[i - 3];
        }
        return f[n];
    }
};

O(N) time and O(N) space. However given the problem statement saying that the n is maximum 37. Both time and space complexity is thus O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —