1137. N-th Tribonacci Number

[mah-shamim]

Discussed in #219

^{Originally posted by mah-shamim August 2, 2024}
Topics: Math, Dynamic Programming, Memoization

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + Tn+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, i.e. answer <= 231 - 1.

Hint:

1. Make an array F of length 38, and set F[0] = 0, F[1] = F[2] = 1.
2. Now write a loop where you set F[n+3] = F[n] + F[n+1] + F[n+2], and return F[n].

[mah-shamim]

The Tribonacci sequence is a variation of the Fibonacci sequence, where each number is the sum of the previous three numbers. In this problem, you're tasked with calculating the N-th Tribonacci number using the given recurrence relation:

• T₀ = 0, T₁ = 1, T₂ = 1
• T_n+3 = T_n + T_n+1 + T_n+2 for n ≥ 0

The goal is to compute T_n efficiently, considering the constraints 0 ≤ n ≤ 37.

Key Points

1. Dynamic Programming Approach: Since each Tribonacci number depends on the previous three, this is an excellent candidate for dynamic programming.
2. Space Optimization: Instead of maintaining a full array for all intermediate values, we only need to track the last three numbers.
3. Constraints: The value of n is relatively small, so both time and space requirements are manageable.

Approach

1. Use a dynamic programming technique to iteratively calculate T_n.
2. Maintain a rolling window of size 3 (space optimization) to track the last three values.
3. Initialize the base cases T₀, T₁, T₂ as 0, 1, and 1, respectively.
4. Use a loop to calculate T_n for n ≥ 3.

Plan

1. Initialize an array dp of size 3 to store the values of T₀, T₁, T₂.
2. Iterate from 3 to n, updating dp using the recurrence relation: dp[i % 3] = dp[0] + dp[1] + dp[2]
3. Return the value of dp[n % 3] as the result.

Let's implement this solution in PHP: 1137. N-th Tribonacci Number

<?php
/**
 * @param Integer $n
 * @return Integer
 */
function tribonacci(int $n): int
{
    $dp = [0, 1, 1];

    for ($i = 3; $i < $n + 1; $i++) {
        $dp[$i % 3] = array_sum($dp);
    }

    return $dp[$n % 3];
}

// Example usage:
$n1 = 4;
$n2 = 25;

echo tribonacci($n1) . "\n"; // Output: 4
echo tribonacci($n2) . "\n"; // Output: 1389537
?>

Explanation:

• Initialization: Start with the first three Tribonacci numbers, T₀ = 0, T₁ = 1, T₂ = 1.
• Loop Logic: For n ≥ 3, calculate the next number as the sum of the previous three. Use modulo operations to store the values cyclically in the array.
• Return Result: Use dp[n % 3] to get the desired Tribonacci number after the loop.

Example Walkthrough

Input: n = 4

1. Initialization: dp = [0, 1, 1] (represents T₀, T₁, T₂).
2. Iteration:
   • i = 3: dp[0] = dp[0] + dp[1] + dp[2] = 0 + 1 + 1 = 2, dp = [2, 1, 1]
   • i = 4: dp[1] = dp[0] + dp[1] + dp[2] = 2 + 1 + 1 = 4, dp = [2, 4, 1]
3. Return Result: dp[4 % 3] = dp[1] = 4

Output: 4

Time Complexity

• Computation: O(n) since we iterate from 3 to n.
• Space: O(1) as we only use a fixed-size array of length 3.

Output for Example

• n = 4: T₄ = 4
• n = 25: T₂₅ = 1389537

The optimized solution efficiently calculates the N-th Tribonacci number using a space-optimized dynamic programming approach. It ensures both correctness and performance, adhering to the constraints provided in the problem.