# 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)

```cpp
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)

```cpp
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 -&gt; base case -&gt; reverse logic, using loop)

```cpp
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)

```cpp
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

| Approach | Time | Space | Notes |
| --- | --- | --- | --- |
| Recursion | O(2^n) | O(n) | Brute force, not practical |
| Memoization | O(n) | O(n) | Top-down + cache |
| Tabulation | O(n) | O(n) | Bottom-up + full array |
| Space Optimized | O(n) | O(1) | Only two variables needed |