Nth Tribonacci Number

Explore how to solve the Nth Tribonacci number problem by applying dynamic programming methods. Understand naive recursion and improve it with memoization and iterative tabulation to optimize time and space complexity.

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