Dynamic Programming using Fibonacci – Approaches
Command Palette
Search for a command to run...
Comments
Join the discussionNo comments yet. Be the first to comment.
Search for a command to run...
No comments yet. Be the first to comment.
Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13...
Formula: f(n) = f(n-1) + f(n-2)
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);
}
Base Case: Return n directly if it's 0 or 1.
Recursive Call: Call resolve(n-1) and resolve(n-2), and return their sum.
No memoization: This leads to repeated computations of the same subproblems.
⏱ Time: O(2^n) 🧠 Space: O(n) (recursion stack) ❌ Recomputes subproblems ✅ Easy to understand
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);
}
Initialize a dp array with -1 to denote unsolved subproblems.
Base Case: Return n if n is 0 or 1.
Memoization Check: If dp[n] is already computed, return it.
Store Result: Calculate the result, store in dp[n], and return.
⏱ Time: O(n) 🧠 Space: O(n) (dp array + recursion stack) ✅ Avoids recomputation
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);
}
Initialize a dp array of size n+1.
Set Base Cases: dp[0] = 0, dp[1] = 1.
Iterate from 2 to n, using previously computed values.
Return dp[n].
✅ Iterative approach ⏱ Time: O(n) 🧠 Space: O(n) ✅ No recursion stack
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);
}
Base Case: Return n if it's 0 or 1.
Track Only Two Values: Use prev and curr to store f(n-2) and f(n-1).
Loop Forward: Update prev and curr for each i till n.
Return curr which holds f(n).
⏱ Time: O(n) 🧠 Space: O(1) ✅ Best optimized
| 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 |