Introduction

The Fibonacci problem is the most common introduction to Dynamic Programming (DP).

Although the mathematical formula is simple, the recursive implementation performs a massive amount of duplicate work.

Fibonacci teaches almost every important Dynamic Programming concept:

• Recursion
• Overlapping Subproblems
• Memoization
• Tabulation
• Space Optimization
• State Transition

For this reason, Fibonacci is often the first DP problem asked in interviews.

---

Problem Statement

Given an integer n, return the nth Fibonacci number.

The sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21...

Formula

F(0)=0

F(1)=1

F(n)=F(n−1)+F(n−2)

---

Example

Input

n = 6

Output

8

Explanation

0

1

1

2

3

5

8

---

Why This Problem Is Important

The recursive solution repeatedly solves the same subproblems.

Example

Fib(5)

├── Fib(4)

│   ├── Fib(3)

│   │   ├── Fib(2)

│   │   └── Fib(1)

│   └── Fib(2)

└── Fib(3)

Notice

Fib(3)

Fib(2)

Fib(1)

are computed multiple times.

Dynamic Programming removes these duplicate calculations.

---

Approach 1 — Pure Recursion

Idea

Solve recursively.

public int fib(int n) {

    if (n <= 1)
        return n;

    return fib(n - 1) + fib(n - 2);

}

---

Internal Working

For

Fib(5)

Calls

graph TD
    Fib_5["Fib(5)"] --> Fib_4["Fib(4)"]
    Fib_4["Fib(4)"] --> Fib_3["Fib(3)"]
    Fib_3["Fib(3)"] --> Fib_2["Fib(2)"]
    Fib_2["Fib(2)"] --> Fib_1["Fib(1)"]
    Fib_1["Fib(1)"] --> Fib_0["Fib(0)"]

Many repeated calls occur.

---

Complexity

Metric	Value
Time	O(2ⁿ)
Space	O(n)

Not recommended for interviews.

---

Approach 2 — Memoization (Top-Down)

Idea

Store already computed answers.

Instead of recomputing

Fib(3)

reuse it.

---

Java Solution

import java.util.Arrays;

public class FibonacciMemo {

    static int[] dp;

    public static int fib(int n) {

        if (n <= 1)
            return n;

        if (dp[n] != -1)
            return dp[n];

        dp[n] = fib(n - 1) + fib(n - 2);

        return dp[n];

    }

    public static void main(String[] args) {

        int n = 8;

        dp = new int[n + 1];

        Arrays.fill(dp, -1);

        System.out.println(fib(n));

    }

}

---

Internal Working

Initially

dp

-1 -1 -1 -1 -1 -1

Compute

graph TD
    Fib_5["Fib(5)"] --> Store["Store"]
    Store["Store"] --> Fib_4["Fib(4)"]
    Fib_4["Fib(4)"] --> Store["Store"]
    Store["Store"] --> Fib_3["Fib(3)"]

Next time

Fib(3)

is needed,

read directly from the cache.

---

Complexity

Metric	Value
Time	O(n)
Space	O(n)

---

Approach 3 — Tabulation (Bottom-Up)

Idea

Start from the smallest subproblem and build upward.

---

DP Table

Index

0 1 2 3 4 5 6

Value

0 1 1 2 3 5 8

---

Java Solution

public class FibonacciTabulation {

    public static int fib(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];

    }

}

---

Complexity

Metric	Value
Time	O(n)
Space	O(n)

---

Approach 4 — Space Optimized DP

Observation

Only

dp[i-1]

dp[i-2]

are required.

No need for the entire array.

---

Java Solution

public class FibonacciOptimized {

    public static int fib(int n) {

        if (n <= 1)
            return n;

        int prev2 = 0;

        int prev1 = 1;

        for (int i = 2; i <= n; i++) {

            int current = prev1 + prev2;

            prev2 = prev1;

            prev1 = current;

        }

        return prev1;

    }

}

---

Complexity

Metric	Value
Time	O(n)
Space	O(1)

This is the preferred interview solution.

---

DP State Design

State

dp[i]

=

Fibonacci value for i

Transition

dp[i]

=

dp[i-1]

+

dp[i-2]

Base Cases

dp[0]=0

dp[1]=1

Answer

dp[n]

---

Comparison

Approach	Time	Space
Recursion	O(2ⁿ)	O(n)
Memoization	O(n)	O(n)
Tabulation	O(n)	O(n)
Optimized DP	O(n)	O(1)

---

Production Use Cases

Although Fibonacci itself is not commonly used in production, the underlying Dynamic Programming technique powers many real-world systems.

Financial Forecasting

Optimize investment growth calculations.

---

AI Decision Systems

Reuse previously solved states instead of recomputation.

---

Route Optimization

Dynamic shortest-path calculations.

---

Recommendation Engines

Reuse computed recommendation scores.

---

Cloud Resource Scheduling

Optimize resource allocation decisions.

---

Bioinformatics

DNA sequence matching using Dynamic Programming.

---

Compiler Optimization

Cache expensive intermediate computations.

---

Image Processing

Reuse overlapping calculations in matrix operations.

---

Common Mistakes

Using Plain Recursion

Avoid exponential recursive solutions.

---

Missing Base Cases

Always define

n == 0

n == 1

---

Forgetting Cache Initialization

Initialize memoization arrays correctly.

---

Wrong Transition Formula

Correct

dp[i]

=

dp[i-1]

+

dp[i-2]

---

Ignoring Space Optimization

Many interviewers expect discussion of reducing space complexity from O(n) to O(1).

---

Interview Tips

Mention these points during interviews:

• Fibonacci demonstrates Overlapping Subproblems and Optimal Substructure.
• Explain why recursion is inefficient.
• Discuss Memoization and Tabulation differences.
• Mention the space-optimized solution.
• Clearly define the DP state and transition.

---

Frequently Asked Interview Questions

1. Why is Fibonacci considered a Dynamic Programming problem?

Answer

Because it has overlapping subproblems and optimal substructure, making cached solutions reusable.

---

2. Why is recursion inefficient?

Answer

It repeatedly computes the same Fibonacci values, leading to exponential time complexity.

---

3. What is Memoization?

Answer

A top-down DP approach that stores previously computed results and reuses them.

---

4. What is Tabulation?

Answer

A bottom-up DP approach that iteratively builds solutions from base cases.

---

5. Which approach is faster?

Answer

Both Memoization and Tabulation run in O(n) time, but Tabulation avoids recursion overhead.

---

6. Can Fibonacci be solved using constant space?

Answer

Yes. Only the previous two values are needed, resulting in O(1) space.

---

7. What are the DP state and transition?

Answer

State: dp[i] stores the ith Fibonacci number.

Transition: dp[i] = dp[i-1] + dp[i-2].

---

8. Where are DP concepts like Fibonacci used in production?

Answer

Financial modeling, recommendation systems, compiler optimization, cloud scheduling, bioinformatics, and route optimization.

---

9. What is the biggest interview mistake?

Answer

Implementing only recursion without discussing Dynamic Programming optimizations.

---

10. Why is Fibonacci taught first in DP?

Answer

Because it introduces the core DP concepts—recursion, overlapping subproblems, memoization, tabulation, and space optimization—in a simple and easy-to-understand problem.

---

Quick Revision

Topic	Summary
Problem	Fibonacci
DP State	dp[i]
Transition	dp[i] = dp[i-1] + dp[i-2]
Best Time Complexity	O(n)
Best Space Complexity	O(1)
Main Concepts	Memoization, Tabulation, Space Optimization
Interview Frequency	⭐⭐⭐⭐⭐

---

Key Takeaways

• Fibonacci is the foundation for understanding Dynamic Programming.
• The recursive solution suffers from repeated calculations due to overlapping subproblems.
• Memoization and Tabulation both reduce the time complexity from O(2ⁿ) to O(n).
• Space optimization further reduces memory usage to O(1) while maintaining linear time.
• Mastering Fibonacci prepares you for more advanced DP problems such as Climbing Stairs, House Robber, Coin Change, Knapsack, and Longest Common Subsequence.

---