Faangprep Logo
Log inStart free
Browse curriculum

Fibonacci Sequence

The Fibonacci sequence is the series in which each number is the sum of the two preceding ones. Calculating its Nth number is a classic first dynamic programming problem.

READY

-

0

-

1

-

2

-

3

-

4

-

5

 

Initialize DP array of size 6

Next

Base cases: dp[0]=0, dp[1]=1

N

5

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. A repeated call finds its value already stored and returns it at once; that cache cell lights up solid blue.
  • Tabulation: Watch the array fill sequentially from left to right.

Complexity analysis

Recursion

Time O(2^n) — exponential, because the same subproblem is recomputed down every branch.

Memoization

Top-down. Time O(n), space O(n) — each subproblem is solved once and cached.

Tabulation

Bottom-up. Time O(n), space O(n) — the same work without the recursion stack.

The gap between the first row and the other two is the whole argument for dynamic programming: nothing about the recurrence changed, only how many times each value is computed.

When to Use

Applications:

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

When NOT to Use

  • Very large n: matrix exponentiation or fast doubling computes F(n) in O(log n) arithmetic steps instead of O(n).
  • Binet's closed form looks like an O(1) shortcut, but in 64-bit floating point it first returns a wrong answer at n = 71, so it is not a substitute for exact integer arithmetic.

How to Identify

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

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Introduction

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.