🔢 Fibonacci Sequence Using Dynamic Programming

The **Fibonacci Sequence** is a series of numbers where **each number is the sum of the two preceding ones**: 


                Fibonacci Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
                Formula: F(n) = F(n-1) + F(n-2)

⚡ Why Optimize Fibonacci Calculation?

  • ❌ **Recursive approach is slow (O(2ⁿ) complexity)**.
  • ✅ **Dynamic Programming reduces time to O(n)**.
  • ✅ **Efficient space optimization can make it O(1)**.

📌 **1. Naïve Recursive Approach (O(2ⁿ))**

A simple recursive approach calculates Fibonacci **inefficiently**. 


                int fibonacci(int n) {
                    if (n <= 1) return n;
                    return fibonacci(n - 1) + fibonacci(n - 2);
                }

❌ **Why is This Slow?**

Because it **recomputes values** multiple times, leading to **exponential time complexity**.

📌 **2. Memoization (Top-Down DP, O(n))**

We **store computed results** to avoid redundant calculations.


                vector memo(100, -1);
            
                int fibonacciMemo(int n) {
                    if (n <= 1) return n;
                    if (memo[n] != -1) return memo[n]; // Check stored value
                    return memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
                }

✅ **Why is Memoization Faster?**

  • 📌 Uses **extra space** (O(n)) but reduces redundant calculations.
  • ⚡ Improves time complexity from **O(2ⁿ) to O(n)**.

📌 **3. Tabulation (Bottom-Up DP, O(n))**

We **build up the solution iteratively** instead of using recursion. 


                int fibonacciTabulation(int n) {
                    vector dp(n + 1);
                    dp[0] = 0, dp[1] = 1;
                    for (int i = 2; i <= n; i++)
                        dp[i] = dp[i - 1] + dp[i - 2];
                    return dp[n];
                }

✅ **Why is Tabulation Better?**

  • 🚀 **No recursive calls, hence avoids stack overflow.**
  • ✅ **Still O(n) time complexity but avoids recursion overhead.**

📌 **4. Space Optimization (O(1) Space, O(n) Time)**

We only need **two previous numbers**, so we can **remove the array** and use two variables. 


                int fibonacciOptimized(int n) {
                    if (n <= 1) return n;
                    int a = 0, b = 1, c;
                    for (int i = 2; i <= n; i++) {
                        c = a + b;
                        a = b;
                        b = c;
                    }
                    return b;
                }

📌 **5. Fibonacci Using Matrix Exponentiation (O(log n))**

We can calculate Fibonacci using **matrix exponentiation**, reducing time complexity to **O(log n)**. 


                void multiply(int F[2][2], int M[2][2]) {
                    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
                    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
                    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
                    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
                    F[0][0] = x; F[0][1] = y;
                    F[1][0] = z; F[1][1] = w;
                }
            
                void power(int F[2][2], int n) {
                    if (n == 0 || n == 1) return;
                    int M[2][2] = {{1, 1}, {1, 0}};
                    power(F, n / 2);
                    multiply(F, F);
                    if (n % 2 != 0) multiply(F, M);
                }
            
                int fibonacciMatrixExponentiation(int n) {
                    if (n == 0) return 0;
                    int F[2][2] = {{1, 1}, {1, 0}};
                    power(F, n - 1);
                    return F[0][0];
                }

✅ **Why Use Matrix Exponentiation?**

  • 🚀 **Much faster (O(log n)) compared to O(n) DP approaches.**
  • ✅ **Used in advanced mathematical and cryptographic applications.**

⏳ Time Complexity Analysis

Approach Time Complexity Space Complexity
Recursion O(2ⁿ) O(n) (Recursion stack)
Memoization (Top-Down DP) O(n) O(n)
Tabulation (Bottom-Up DP) O(n) O(n)
Space Optimized DP O(n) O(1)
Matrix Exponentiation O(log n) O(1)

🌍 Real-World Applications of Fibonacci Sequence

  • 📈 **Stock Market Analysis** – Predicting trends.
  • 🔢 **Cryptography & Encoding Algorithms**.
  • 🎮 **Procedural Game Development & Fractals**.
  • 📡 **Data Structures & Algorithms (Tree Generation, Heap Management).**

🔗 Next Topics