N-th Tribonacci Number - Video Solutions

Problem Overview: The Tribonacci sequence is similar to Fibonacci, but each number is the sum of the previous three values instead of two. You are given an integer n and must return the n-th Tribonacci number where T0 = 0, T1 = 1, T2 = 1, and Tn = T(n-1) + T(n-2) + T(n-3) for n ≥ 3. The task is essentially evaluating this recurrence efficiently.

Approach 1: Recursive Solution with Memoization (Time: O(n), Space: O(n))

The direct recursive definition mirrors the mathematical recurrence: compute T(n-1), T(n-2), and T(n-3) and sum them. Pure recursion recomputes the same values many times, leading to exponential complexity. Memoization fixes that by storing previously computed results in a cache (array or hash map). Each state T(i) is computed once and reused afterward. This approach clearly demonstrates how overlapping subproblems appear in dynamic programming, and it’s a natural way to translate the recurrence into code.

Approach 2: Iterative Dynamic Programming (Time: O(n), Space: O(1))

The recurrence only depends on the previous three values. Instead of storing the entire DP table, you can track just three variables representing T(n-3), T(n-2), and T(n-1). Start from the base cases and iterate from 3 to n, computing the next Tribonacci value as the sum of the three tracked values. After each iteration, shift the variables forward. This reduces space to constant while keeping the same linear runtime. The approach is a classic bottom-up dynamic programming pattern and avoids recursion overhead.

This iterative strategy works because the Tribonacci recurrence forms a simple dependency chain. At step i, all required values have already been computed in earlier iterations. Instead of recursion stacks or large arrays, you only keep the minimal state required to produce the next result.

Recommended for interviews: The iterative dynamic programming approach with three variables is the expected solution. It runs in O(n) time and O(1) space and demonstrates that you understand how to optimize a recurrence relation. Showing the memoized recursion first can help explain the transition from naive recursion to memoization and finally to an iterative DP implementation, which is typically what interviewers want to see.