Introduction

The Fibonacci sequence is one of the most important problems in Dynamic Programming.

Each number is formed by adding the previous two numbers.

Sequence:

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

Formula:

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

Example:

n = 6Output = 8

Explanation:

F(6) = F(5) + F(4) = 5 + 3 = 8

This problem introduces:

Dynamic Programming

Constraints

0 <= n <= 45

Why Recursion is Slow

Recursive solution:

F(5)├── F(4)
│   ├── F(3)
│   └── F(2)
│
└── F(3)
    ├── F(2)
    └── F(1)

Notice:

F(3) is calculated multiple times.

This is called:

Overlapping Subproblems

Dynamic Programming solves this issue.

Approach 1 : Memoization (Top Down DP)

Explanation

Store previously calculated answers.

Steps:

  1. Solve recursively.
  2. Save result.
  3. Reuse stored result.
  4. Avoid repeated calculations.

Formula:

dp[n] = dp[n-1] + dp[n-2]

Dry Run

n = 5F(5) = F(4) + F(3)

Store:
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5

Approach 2 : Tabulation (Bottom Up DP)

Explanation

Build answers from smaller values.

Steps:

  1. Create DP array.
  2. Initialize base cases.
  3. Fill array from left to right.
  4. Return last value.

Example:

dp[0] = 0dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 3
dp[5] = 5

Approach 3 : Space Optimized DP

Explanation

Only previous two values are needed.

Instead of storing entire DP array:

prev2 prev1

Update them while moving forward.

This gives:

O(1) space

Practice

Complexity Analysis

Memoization
Time Complexity: O(n)
Space Complexity: O(n)

Tabulation

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

Space Optimized DP

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

Why This Problem is Important

This problem teaches:

  • Recursion
  • Memoization
  • Tabulation
  • Space Optimization
  • Dynamic Programming Fundamentals

Real-World Applications

Fibonacci concepts appear in:

  • Resource Allocation
  • Financial Modeling
  • Algorithm Optimization
  • Tree Structures
  • Mathematical Computing

Common Beginner Mistakes

  • Using plain recursion
  • Forgetting base cases
  • Wrong DP initialization
  • Incorrect loop boundaries
  • Not optimizing space

Interview Tip

Interviewers often expect progression:

Recursion→ Memoization
→ Tabulation
→ Space Optimization

Always explain:

  • overlapping subproblems
  • why DP works
  • how space optimization is achieved

Related Questions

  • Climbing Stairs
  • Min Cost Climbing Stairs
  • House Robber
  • Coin Change
  • Longest Increasing Subsequence

Final Takeaway

Fibonacci is the starting point of Dynamic Programming.

It teaches:

  • how DP is discovered
  • why recursion becomes expensive
  • how memoization saves work
  • how tabulation builds solutions
  • how space optimization improves efficiency

Mastering Fibonacci makes every future DP problem easier to understand.