Fibonacci with DP
In this page:
Fibonacci DP
Plain recursive Fibonacci recomputes the same smaller Fibonacci values over and over, so its running time grows exponentially; storing each value the first time it's computed turns that same recursion into a fast, DP-powered version.
Example: Fibonacci DP
#include <iostream>
using namespace std;
int main() {
int dp[11]; dp[0]=0; dp[1]=1;
for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
cout << "Stored values turn exponential recursion into fib(10) = " << dp[10] << " in linear time";
return 0;
}public class Main {
public static void main(String[] args) {
int[] dp = new int[11]; dp[0]=0; dp[1]=1;
for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
System.out.println("Stored values turn exponential recursion into fib(10) = " + dp[10] + " in linear time");
}
}dp = [0]*11
dp[1] = 1
for i in range(2, 11):
dp[i] = dp[i-1] + dp[i-2]
print(f"Stored values turn exponential recursion into fib(10) = {dp[10]} in linear time")#include <stdio.h>
int main() {
int dp[11]; dp[0]=0; dp[1]=1;
for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
printf("Stored values turn exponential recursion into fib(10) = %d in linear time", dp[10]);
return 0;
}Login to try C/C++/Java code in the editor
Space Optimization
Since computing fib(n) only ever needs the two values immediately before it, you don't need to store the whole table — keeping just two running variables and updating them each step reduces the memory from O(n) down to O(1).
Example: Space Optimization
#include <iostream>
using namespace std;
int main() {
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= 10; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }
cout << "Only 2 variables needed, fib(10) = " << prev1;
return 0;
}public class Main {
public static void main(String[] args) {
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= 10; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }
System.out.println("Only 2 variables needed, fib(10) = " + prev1);
}
}prev2, prev1 = 0, 1
for i in range(2, 11):
prev2, prev1 = prev1, prev1 + prev2
print("Only 2 variables needed, fib(10) =", prev1)#include <stdio.h>
int main() {
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= 10; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }
printf("Only 2 variables needed, fib(10) = %d", prev1);
return 0;
}Login to try C/C++/Java code in the editor
Memoization
A memoized version keeps the natural top-down recursive structure (fib(n) calls fib(n-1) and fib(n-2)) but checks a cache first, so each distinct value of n is computed only once no matter how many times it's requested.
Example: Memoization
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int,int> cache;
int fib(int n) {
if (n <= 1) return n;
if (cache.count(n)) return cache[n];
return cache[n] = fib(n-1) + fib(n-2);
}
int main() { cout << "Recursive shape kept, fib(10) = " << fib(10); return 0; }import java.util.*;
public class Main {
static Map<Integer,Integer> cache = new HashMap<>();
static int fib(int n) {
if (n <= 1) return n;
if (cache.containsKey(n)) return cache.get(n);
int r = fib(n-1) + fib(n-2);
cache.put(n, r);
return r;
}
public static void main(String[] args) { System.out.println("Recursive shape kept, fib(10) = " + fib(10)); }
}cache = {}
def fib(n):
if n <= 1:
return n
if n in cache:
return cache[n]
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
print("Recursive shape kept, fib(10) =", fib(10))#include <stdio.h>
int cache[11]={0}, computed[11]={0};
int fib(int n) {
if (n <= 1) return n;
if (computed[n]) return cache[n];
computed[n] = 1;
return cache[n] = fib(n-1) + fib(n-2);
}
int main() { printf("Recursive shape kept, fib(10) = %d", fib(10)); return 0; }Login to try C/C++/Java code in the editor
Complexity
Storing results turns the exponential time of naive recursion into linear time, since each of the n distinct subproblems is now solved exactly once instead of being recomputed along every branching recursive call.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Naive recursion: O(2^n); DP (memo or tabulation): O(n), each subproblem solved once";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Naive recursion: O(2^n); DP (memo or tabulation): O(n), each subproblem solved once");
}
}print("Naive recursion: O(2^n); DP (memo or tabulation): O(n), each subproblem solved once")#include <stdio.h>
int main() {
printf("Naive recursion: O(2^n); DP (memo or tabulation): O(n), each subproblem solved once");
return 0;
}Login to try C/C++/Java code in the editor
Practice
Fibonacci is usually the first DP example taught because its overlapping subproblems are easy to see directly in the recursion tree, making it a clean way to understand why memoization and tabulation help before tackling harder problems.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Fibonacci's recursion tree makes overlapping subproblems easy to see -- the classic first DP example";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Fibonacci's recursion tree makes overlapping subproblems easy to see -- the classic first DP example");
}
}print("Fibonacci's recursion tree makes overlapping subproblems easy to see -- the classic first DP example")#include <stdio.h>
int main() {
printf("Fibonacci's recursion tree makes overlapping subproblems easy to see -- the classic first DP example");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: