Fibonacci Series using DP
Definition
The Fibonacci Sequence is a series where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8…
How it Works (The DP Way)
A normal recursive approach calculates fib(5) by calling fib(4) and fib(3). But fib(4) also calls fib(3). We end up calculating fib(3) twice!
- DP Fix: Calculate fib(3) once, save it in an array memo[3]. The next time it’s needed, just return memo[3].
Code Example (Top Down)
PythonJavaCC++
# Fibonacci using Dynamic Programming (Memoization)
memo = [-1] * 100
def fib(n):
if n <= 1:
return n
# If value already computed
if memo[n] != -1:
return memo[n]
# Compute and store
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(10)) # 55
import java.util.Arrays;
public class FibonacciDP {
static int[] memo = new int[100];
public static int fib(int n) {
if (n <= 1)
return n;
if (memo[n] != -1)
return memo[n];
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
public static void main(String[] args) {
Arrays.fill(memo, -1);
System.out.println(fib(10)); // 55
}
}
#include <stdio.h>
int memo[100];
int fib(int n) {
if (n <= 1)
return n;
if (memo[n] != -1)
return memo[n];
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
int main() {
for (int i = 0; i < 100; i++)
memo[i] = -1;
printf("%d\n", fib(10)); // 55
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
vector<int> memo(100, -1);
int fib(int n) {
if (n <= 1)
return n;
if (memo[n] != -1)
return memo[n];
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
int main() {
cout << fib(10); // 55
return 0;
}
Complexity Analysis
- Time Complexity: O(N). We calculate each number from 0 to N exactly once. (Naive recursion is O(2^N) terrible)
- Space Complexity: O(N) for the array and recursion stack.