Dynamic Programming using Fibonacci – Approaches

Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13...
Formula: f(n) = f(n-1) + f(n-2)

---

1. 🚀 Recursion (Brute Force)

int rec(int n) {
    if (n == 0 || n == 1) return n;
    return rec(n - 1) + rec(n - 2);
}

int fib(int n) {
    return rec(n);
}

Steps:

1. Base Case: Return n directly if it's 0 or 1.

2. Recursive Call: Call resolve(n-1) and resolve(n-2), and return their sum.

3. No memoization: This leads to repeated computations of the same subproblems.

Time & Space:

⏱ Time: O(2^n) 🧠 Space: O(n) (recursion stack) ❌ Recomputes subproblems ✅ Easy to understand

2. 🧰 Top-Down (Memoization): (dp-array -> logic -> base case, using recursion)

int topdown(vector<int>& dp, int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    if (dp[n] == -1) {
        dp[n] = topdown(dp, n - 1) + topdown(dp, n - 2);
    }
    return dp[n];
}

int fib(int n) {
    vector<int> dp(n + 1, -1);
    return topdown(dp, n);
}

Steps:

1. Initialize a dp array with -1 to denote unsolved subproblems.

2. Base Case: Return n if n is 0 or 1.

3. Memoization Check: If dp[n] is already computed, return it.

4. Store Result: Calculate the result, store in dp[n], and return.

Time & Space:

⏱ Time: O(n) 🧠 Space: O(n) (dp array + recursion stack) ✅ Avoids recomputation

3. 📚 Bottom-Up (Tabulation): (dp-array -> base case -> reverse logic, using loop)

int tabsolve(int n) {
    if (n == 0) return 0;

    vector<int> dp(n + 1, -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];
}

int fib(int n) {
    return tabsolve(n);
}

Steps:

1. Initialize a dp array of size n+1.

2. Set Base Cases: dp[0] = 0, dp[1] = 1.

3. Iterate from 2 to n, using previously computed values.

4. Return dp[n].

Time & Space:

✅ Iterative approach ⏱ Time: O(n) 🧠 Space: O(n) ✅ No recursion stack

4. 🧪 Space Optimized (Tabulation)

int tabsolve(int n) {
    if (n == 0 || n == 1) return n;

    int prev = 0, curr = 1;

    for (int i = 2; i <= n; i++) {
        int temp = curr + prev;
        prev = curr;
        curr = temp;
    }

    return curr;
}

int fib(int n) {
    return tabsolve(n);
}

Steps:

1. Base Case: Return n if it's 0 or 1.

2. Track Only Two Values: Use prev and curr to store f(n-2) and f(n-1).

3. Loop Forward: Update prev and curr for each i till n.

4. Return curr which holds f(n).

Time & Space:

⏱ Time: O(n) 🧠 Space: O(1) ✅ Best optimized

🎯 Summary