Theory - Fibonacci

Problem Foundation

Original Problem:
Given an integer n, compute the n-th Fibonacci number:

Base Cases: F(0) = 0, F(1) = 1
Recurrence: F(n) = F(n-1) + F(n-2) for n ≥ 2

Intuition & Recurrence:

Each number is the sum of the two preceding ones.

Example:

F(2) = F(1) + F(0) = 1 + 0 = 1  
F(3) = F(2) + F(1) = 1 + 1 = 2  
F(4) = F(3) + F(2) = 2 + 1 = 3

Recursion Tree for F(5):

F5
├── F4
│   ├── F3
│   │   ├── F2
│   │   │   ├── F1
│   │   │   └── F0
│   │   └── F1
│   └── F2
│       ├── F1
│       └── F0
└── F3
    ├── F2
    │   ├── F1
    │   └── F0
    └── F1

Key Insight:
Exponential time complexity O(2ⁿ) due to repeated calculations (e.g., F(2) is computed multiple times).

Pattern Derivation

1. Naive Recursion

Java Code:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Dry Run (n = 4):

fib(4)
→ fib(3) + fib(2)
→ (fib(2) + fib(1)) + (fib(1) + fib(0)) → ...

Total Calls: 9

Complexity:

Time: O(2ⁿ)
Space: O(n) (recursion stack)

2. Memoization (Top-Down DP)

Intuition: Cache results to avoid recomputation.

Java Code:

int fibMemo(int n, int[] cache) {
    if (n <= 1) return n;
    if (cache[n] != -1) return cache[n];

    cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
    return cache[n];
}

// Usage:
int[] cache = new int[n + 1];
Arrays.fill(cache, -1);
return fibMemo(n, cache);

Dry Run (n = 4):

cache[2] = 1
cache[3] = 2
cache[4] = 3

Complexity:

Time: O(n)
Space: O(n) (cache + recursion stack)

3. Tabulation (Bottom-Up DP)

Intuition: Fill the DP table from base cases.

Java Code:

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];
}

Dry Run (n = 4):

i	dp[i]	Computation
0	0	Base case
1	1	Base case
2	1	dp[1] + dp[0]
3	2	dp[2] + dp[1]
4	3	dp[3] + dp[2]

Complexity:

Time: O(n)
Space: O(n)

4. Space-Optimized Tabulation

Intuition: Track only last two values instead of full DP array.

Java Code:

int fibOpt(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;

    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Dry Run (n = 4):

i	prev2	prev1	curr
2	0	1	1
3	1	1	2
4	1	2	3

Complexity:

Time: O(n)
Space: O(1)

Interview Insights

Why Fibonacci is the "Hello World" of DP:

Demonstrates:
- Overlapping subproblems
- Optimal substructure
- Transition relation
- Space optimization potential

Comparison of Approaches:

Approach	Code Complexity	Space	Readability	Use Case
Naive Recursion	Simple	O(n)	High	Never in practice
Memoization	Moderate	O(n)	Medium	Top-down problems
Tabulation	Moderate	O(n)	High	General DP use-case
Space Optimized DP	Simple	O(1)	Medium	Production code

Extensions and Variants

Climbing Stairs (LeetCode 70):
Ways to climb n stairs using 1 or 2 steps:
ways(n) = ways(n-1) + ways(n-2) → Same as Fibonacci
Tiling Problem (2 × n board):
Ways to tile a 2 × n board using 2 × 1 tiles → Same recurrence.

Custom Steps (e.g., steps = {1, 3, 5}):

dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 5]

Tribonacci Sequence:

T(n) = T(n-1) + T(n-2) + T(n-3)  
Base: T(0)=0, T(1)=1, T(2)=1

Decode Ways (LeetCode 91):
Number of ways to decode a digit string → DP with conditional transitions, often Fibonacci-like.

Java Implementation: Climbing Stairs with Custom Steps

Problem: Count the number of ways to reach the n-th stair using any step size from a given set.

Java Code:

int climbStairs(int n, int[] steps) {
    int[] dp = new int[n + 1];
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int step : steps) {
            if (i >= step) {
                dp[i] += dp[i - step];
            }
        }
    }
    return dp[n];
}

Dry Run (n = 3, steps = {1, 2}):

i	Valid Steps	dp[i]	Computation
0	-	1	Base case
1		1	dp[0]
2		2	dp[1] + dp[0] = 1 + 1
3		3	dp[2] + dp[1] = 2 + 1

Answer: 3 ways → [1+1+1], [1+2], [2+1]

Complexity:

Time: O(n × k) where k = steps.length
Space: O(n)

Key Takeaways

Fibonacci is the foundation of 1D DP problems involving additive state transitions.
Approach ladder:
1. Naive recursion
2. Add memoization
3. Convert to tabulation
4. Optimize space
Always check for:
- Overlapping subproblems
- Optimal substructure
- Clear base cases
- State transition relations