Fibonacci Numbers

Explore how to find the nth Fibonacci number by applying dynamic programming strategies to optimize recursive approaches. Understand naive recursion, memoization with top-down methods, and bottom-up tabulation. Learn to reduce time and space complexity for efficient coding solutions.

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