Faangprep Logo
LoginRegister
Browse Curriculum

Fibonacci Sequence

The Hello World of Dynamic Programming. Calculates the Nth number where each number is the sum of the two preceding ones.

Ready

N =

5

1x

Intuition

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8...) is defined by F(n) = F(n-1) + F(n-2). A naive recursive solution recalculates the same values endlessly (e.g., F(5) calls F(3) twice, F(2) three times). DP fixes this by solving each subproblem exactly once.

Concept

We can optimize the calculation in two ways:

  • Memoization (Top-Down): Keep the recursive logic, but before returning, save the result in an array. Before computing, check if the value is already saved.
  • Tabulation (Bottom-Up): Start from base cases F(0)=0, F(1)=1 and iteratively compute F(2), then F(3), up to F(n).

How it Works

Tabulation Approach:

  1. Create an array `dp` of size N+1.
  2. Set `dp[0] = 0`, `dp[1] = 1`.
  3. Loop from i = 2 to N:
  4. Set `dp[i] = dp[i-1] + dp[i-2]`.
  5. Return `dp[N]`.

Step-by-Step Breakdown

Watch the visualization:

  • Recursion: Watch the stack grow deep and wide. Notice repeated identical calls.
  • Memoization: Watch the "cache" fill up. Repeated calls return instantly (green).
  • Tabulation: Watch the array fill sequentially from left to right.
Complexity Analysis

Recursion

Time: O(2^n) - Exponential

Memoization (Top-Down)

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

Tabulation (Bottom-Up)

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

When to Use

Applications:

  • Calculating growth models (rabbits, population).
  • Stepping stone for problems like "Climbing Stairs" or "Decode Ways".

When NOT to Use

  • Closed Form exists: Uses Binet's Formula to calculate in O(\log n) or even O(1) with floating point, though DP is educational.

How to Identify

"F(n) depends on F(n-1)...", "Recurrence relation".

Previous

1D DP

Next

Climbing Stairs

Frequently Asked Questions

Fibonacci DP vs Recursion?

Simple recursion for Fibonacci has O(2^n) time complexity. Using DP, this is reduced to O(n) time and O(n) space (or O(1) space with optimization).

Recursive State Transition?

The core formula is f(n) = f(n-1) + f(n-2), where f(0)=0 and f(1)=1.

Space optimization?

Since you only need the previous TWO values, you can optimize space by using two variables instead of a full DP array.