Tribonacci Sequence Solution

This problem asks us to find the nth Tribonacci number, where the sequence is defined as T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

1. Naive Recursive Solution

A straightforward approach is to use recursion directly based on the definition.

def tribonacci_recursive(n):
 if n == 0:
 return 0
 if n == 1 or n == 2:
 return 1
 return tribonacci_recursive(n-1) + tribonacci_recursive(n-2) + tribonacci_recursive(n-3)

This solution is simple but highly inefficient due to repeated calculations.

• Time Complexity: O(3^n) - Each call branches into three more calls.
• Space Complexity: O(n) - Due to the call stack.

2. Optimal Solution: Dynamic Programming (Iterative)

To avoid redundant calculations, we can use dynamic programming. Since we only need the last three Tribonacci numbers to calculate the next one, we can store them in variables and iterate.

def tribonacci_dp(n):
 if n == 0:
 return 0
 if n == 1 or n == 2:
 return 1

 t0, t1, t2 = 0, 1, 1
 for i in range(3, n + 1):
 t0, t1, t2 = t1, t2, t0 + t1 + t2
 return t2

• Time Complexity: O(n) - We iterate from 3 to n.
• Space Complexity: O(1) - We use a constant amount of extra space.

3. Edge Cases

• n = 0: Return 0.
• n = 1 or n = 2: Return 1.
• n > 2: Apply the Tribonacci formula iteratively.

4. Python Code

Here's the dynamic programming solution:

def tribonacci(n):
 if n == 0:
 return 0
 if n == 1 or n == 2:
 return 1

 t0, t1, t2 = 0, 1, 1
 for i in range(3, n + 1):
 tn = t0 + t1 + t2
 t0, t1, t2 = t1, t2, tn
 return t2