N-th Tribonacci Number

Difficulty: Easy | Acceptance: 63.20% | Paid: No Topics: Math, Dynamic Programming, Memoization

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

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 1: Recursion (Brute Force)
• Approach 2: Memoization (Top-Down DP)
• Approach 3: Iterative (Bottom-Up DP)

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 1: Recursion (Brute Force)

Intuition Directly translate the mathematical definition of the Tribonacci sequence into a recursive function. The function calls itself to calculate the previous three values.

Steps

• Handle base cases: if n is 0 return 0, if n is 1 or 2 return 1.
• For n > 2, recursively call the function for n-1, n-2, and n-3.
• Sum the results of the three recursive calls and return the value.

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n < 3:
            return 1
        return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)

Complexity

• Time: O(3ⁿ) - Each call branches into 3 calls, leading to exponential growth.
• Space: O(n) - Recursion stack depth.
• Notes: This approach is too slow for larger n due to repeated calculations.

Approach 2: Memoization (Top-Down DP)

Intuition Optimize the recursive approach by storing the results of previously computed values in a hash map or array. This avoids redundant calculations.

Steps

• Create a memoization storage (array or map).
• Define a helper function that checks if the value for n is already in storage.
• If it is, return the stored value.
• If not, calculate it recursively, store it, and return it.

class Solution:
    def tribonacci(self, n: int) -> int:
        memo = {}
        def helper(k):
            if k == 0: return 0
            if k < 3: return 1
            if k in memo: return memo[k]
            memo[k] = helper(k - 1) + helper(k - 2) + helper(k - 3)
            return memo[k]
        return helper(n)

Complexity

• Time: O(n) - Each value from 0 to n is calculated exactly once.
• Space: O(n) - For the memoization array and recursion stack.
• Notes: Significantly faster than brute force recursion.

Approach 3: Iterative (Bottom-Up DP)

Intuition Build the sequence from the bottom up using three variables to store the last three Tribonacci numbers. This eliminates recursion overhead and extra space for memoization.

Steps

• Handle base cases for n = 0, 1, 2.
• Initialize three variables a, b, c to represent T0, T1, T2.
• Iterate from 3 up to n.
• In each iteration, calculate the next value as the sum of a, b, and c.
• Shift the values: a becomes b, b becomes c, c becomes the new sum.
• Return c after the loop finishes.

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0: return 0
        if n < 3: return 1
        a, b, c = 0, 1, 1
        for _ in range(3, n + 1):
            next_val = a + b + c
            a, b, c = b, c, next_val
        return c

Complexity

• Time: O(n) - Single loop from 3 to n.
• Space: O(1) - Only three integer variables are used.
• Notes: This is the most optimal approach for this problem in terms of space complexity.