Fibonacci Series — From Recursion to Space-Optimized DP
Solve this ProblemTest Case 1:
Constraints
- ◆
0 ≤ n ≤ 25 - ◆
fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n ≥ 2
Pseudocode & Visual Walkthrough
1. Recursive Approach
Pseudocode plus the full recursion tree for f(5). Every call that isn't a base case branches into two more, so the call count doubles at every level — O(2ⁿ) calls, O(n) stack space.
2. Memoization — Top-Down
Same recursion tree, but every result is cached the first time it's computed. The dp array updates as the tree is explored, so each distinct value is ever computed once — O(n) time.
3. Tabulation — Bottom-Up
No recursion at all: the dp array is filled iteratively from dp[0] upward until dp[n] is reached. O(n) time, O(n) space, no call stack.
4. Space Optimization
Only the last two values are ever needed to compute the next one, so the whole dp array collapses into two rolling variables — O(n) time, O(1) space.
Try the Dry Run
Approach & Solutions
Plain Recursion — Recompute Every SubproblemBrute
Translate the definition directly into a recursive function: fib(n) is fib(n-1) plus fib(n-2), with fib(0) and fib(1) as base cases. This is correct, but it recomputes the same smaller values over and over — fib(3), for instance, gets fully recalculated from scratch every single time some larger call happens to need it, and there can be exponentially many such repeats as n grows.
O(2ⁿ)O(n) call-stack space1class Solution {
2 public int fibonacciSeries(int n) {
3 if (n <= 1) return n;
4 return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
5 }
6}Memoization — Top-Down with CachingBetter
Keep the exact same recursive structure, but remember every answer the first time it's computed, in an array indexed by n. Before doing any real work, check whether this n has already been solved — if so, hand back the cached answer immediately instead of recursing again. Since there are only n+1 distinct subproblems total, and each is now computed exactly once, the exponential blowup collapses to linear.
O(n)O(n)1class Solution {
2 public int fibonacciSeries(int n) {
3 int[] memo = new int[n + 1];
4 for (int i = 0; i <= n; i++) memo[i] = -1;
5 return helper(n, memo);
6 }
7
8 private int helper(int n, int[] memo) {
9 if (n <= 1) return n;
10 if (memo[n] != -1) return memo[n];
11 memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
12 return memo[n];
13 }
14}Tabulation — Bottom-Up DP ArrayBetter
Flip memoization around: instead of recursing down from n and caching on the way back up, build the answer from the bottom. Seed a dp array with the two known base values, dp[0] = 0 and dp[1] = 1, then fill every later index as the sum of the two before it. By the time the loop reaches n, dp[n] already holds the answer — and there's no recursion or call stack involved at all.
O(n)O(n)1class Solution {
2 public int fibonacciSeries(int n) {
3 if (n <= 1) return n;
4 int[] dp = new int[n + 1];
5 dp[0] = 0;
6 dp[1] = 1;
7 for (int i = 2; i <= n; i++) {
8 dp[i] = dp[i - 1] + dp[i - 2];
9 }
10 return dp[n];
11 }
12}Space Optimization — Two Rolling VariablesOptimal
Notice that filling dp[i] only ever looks at dp[i-1] and dp[i-2] — nothing further back is ever touched again. So there's no real need to keep the whole array: two rolling variables, prev2 and prev1, are enough. At each step compute curr = prev1 + prev2, then slide the window forward. Same O(n) time as tabulation, but with constant space instead of linear.
O(n)O(1)1class Solution {
2 public int fibonacciSeries(int n) {
3 if (n <= 1) return n;
4 int prev2 = 0, prev1 = 1, curr = 0;
5 for (int i = 2; i <= n; i++) {
6 curr = prev1 + prev2;
7 prev2 = prev1;
8 prev1 = curr;
9 }
10 return prev1;
11 }
12}