Fibonacci Numbers

Explore how to compute the nth Fibonacci number by applying recursive solutions and enhancing them with dynamic programming techniques such as memoization and tabulation. Understand efficiency gains in time and space complexity using these approaches in C++.

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