1137. N-th Tribonacci Number

1137. N-th Tribonacci Number

Difficulty: Easy

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].

Solution:

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
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub