Fibonacci Numbers

Explore how to compute the nth Fibonacci number by mastering naive recursion and optimizing with dynamic programming patterns. Learn top-down memoization and bottom-up tabulation approaches to improve time and space efficiency in finding Fibonacci numbers.

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

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

The Fibonacci sequence is defined as:

$F_0 = 0,\space F_1 = 1,\space F_n = F_{n-1} + F_{n-2},\space$

...

1.Getting Started

2.0/1 Knapsack

3.Unbounded Knapsack

4.Recursive Numbers

5.Longest Common Substring

6.Palindromic Subsequence

7.Conclusion

Fibonacci Numbers

Statement