Fibonacci DP
Fibonacci numbers are the classic DP example: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Without DP, the naive recursion is exponential (O(2^n)). With DP, we get O(n).
We'll implement both memoization and tabulation.
Memoization (top-down):
int fibMemo(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
return memo[n];
}
Tabulation (bottom-up):
int fibTab(int n) {
if (n <= 1) return n;
int[] dp = new int[n+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];
}
We can also optimize space to O(1) by storing only the last two values.
Two Minute Drill
- Fibonacci is a classic DP problem.
- Naive recursion is O(2^n); DP gives O(n).
- Memoization: recursion + cache.
- Tabulation: iterative table.
- Space can be optimized to O(1).
Need more clarification?
Drop us an email at career@quipoinfotech.com