Nth Tribonacci Number

Explore how to find the nth Tribonacci number by applying recursive and dynamic programming methods. Understand the limitations of naive recursion and improve your solutions using memoization and bottom-up approaches. This lesson shows how to optimize time and space complexity to handle larger inputs efficiently.

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