Nth Tribonacci Number

Explore how to compute the nth Tribonacci number by starting from a naive recursive approach and optimizing it using memoization and bottom-up techniques. Understand time and space complexity trade-offs and improve solutions to constant space usage while maintaining efficient run time.

We'll cover the following...

Statement
Examples
Try it yourself
Solution
- Naive approach
  - Time complexity
  - Space complexity
- Optimized solution using dynamic programming
  - Top-down solution
    - Time complexity
    - Space complexity
  - Bottom-up solution

Statement

Tribonacci numbers are a sequence of numbers where each number is the sum of the three preceding numbers. Your task is to find the $n^{th}$ Tribonacci number.

The Tribonacci sequence is defined as:

$T_0 = 0,\space T_1 = 1,\space T_2 = 1$ , and $\space T_n = T_{n-1} + T_{n-2} + T_{n-3}, \space$

...

1.Getting Started

2.0/1 Knapsack

3.Unbounded Knapsack

4.Recursive Numbers

5.Longest Common Substring

6.Palindromic Subsequence

7.Conclusion

Nth Tribonacci Number

Statement