N-th Tribonacci Number

Problem Statement

The Tribonacci sequence is a series where each number (or term) after the first three is the sum of the preceding three terms. The sequence starts with ( T_0 = 0 ), ( T_1 = 1 ), and ( T_2 = 1 ). Subsequent terms are defined by the relationship ( T_{n+3} = T_n + T_{n+1} + T_{n+2} ) for ( n ) greater than or equal to 0. Given a number ( n ), the task is to compute and return the ( n )th value of the Tribonacci sequence, denoted as ( T_n ).

Examples

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.

Approach and Intuition

The Tribonacci sequence, inspired by the Fibonacci series, expands on the concept by summing the last three terms instead of two. Understanding the problem through the given examples can elucidate the approach:

Example Analysis

1. Understanding the Sequence Expansion:
   • For ( n = 4 ):
     • Build from known initial values: ( T_3 = T_0 + T_1 + T_2 = 0 + 1 + 1 = 2 )
     • Then, ( T_4 = T_1 + T_2 + T_3 = 1 + 1 + 2 = 4 )
     • Hence the output is 4.
   • For ( n = 25 ):
     • This would require iterating or recursively calculating up to the 25th term starting from the initial defined terms ( T_0, T_1, T_2 ).
     • The output for ( T_{25} ) is 1389537 given the sum of the previous three terms up to that point.

Intuition and Algorithm Steps:

The operation ( T_{n+3} = T_n + T_{n+1} + T_{n+2} ) suggests the use of an iterative approach or dynamic programming to store previously computed terms for efficient computation:

1. Begin by defining the base cases:
   • ( T_0 = 0 ), ( T_1 = 1 ), ( T_2 = 1 )
2. Use a loop to fill in the subsequent terms from 3 to ( n ) using the values of the three preceding terms.
3. For each iteration ( i ) from 3 to ( n ), update the value at ( T_i ) as ( T_{i-3} + T_{i-2} + T_{i-1} ).
4. The final value ( T_n ) is directly returned at the end of the computation.

Constraints management:

• Values of ( n ) range between 0 and 37, ensuring computation remains manageable within the fixed iterations.
• Storing only the necessary terms or even the last three terms in each step can optimize space usage while aligning with the 32-bit integer limits on the results.

Solutions

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