Problem Statement
What is the space complexity of the optimized Fibonacci DP solution?
Explanation
The Fibonacci sequence can be optimized to use O of 1 space instead of O of n by observing that we only need the last two values to compute the next value. We can use two variables instead of an entire array.
The standard tabulation approach uses an array of size n plus 1, giving O of n space. However, since F of i only depends on F of i minus 1 and F of i minus 2, we can maintain just these two values in variables, updating them as we iterate. This space optimization technique is common in DP problems where the current state depends only on a fixed number of previous states.
Code Solution
SolutionRead Only
// Standard DP - O(n) space
int fibStandard(int 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];
}
// Space: O(n)
// Optimized DP - O(1) space
int fibOptimized(int n) {
if (n <= 1) return n;
int prev2 = 0; // F(i-2)
int prev1 = 1; // F(i-1)
int curr = 0;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1; // Shift values
prev1 = curr;
}
return curr;
}
// Space: O(1) - only 3 variables!
// General pattern for space optimization:
// If dp[i] depends only on dp[i-1], dp[i-2], ...
// Use variables instead of arrayPractice Sets
This question appears in the following practice sets:
