Oh My Algorithm
Algorithm Guidecomplexity: O(n)

Fibonacci Sequence (DP)

Dynamic programming stores and reuses previously computed subsolutions in a table to eliminate redundant work. It's the classic memoization example, pulling naive recursion from O(2^n) down to O(n).

01Fibonacci Sequence (DP)

Computing Fibonacci with DP. Writing the previous two answers down and reusing them means nothing is computed twice, so the 10th arrives in O(n).

The table starts empty — nothing has been computed yet.

Only the two starting cells are filled in by hand: the 0th is 0, the 1st is 1. Everything else follows from these.

Add the previous two cells · 1 + 0 = 1. Both are already written down, so one addition does it.

Add the previous two cells · 1 + 1 = 2.

Add the previous two cells · 2 + 1 = 3.

Add the previous two cells · 3 + 2 = 5.

Add the previous two cells · 5 + 3 = 8.

Add the previous two cells · 8 + 5 = 13.

Add the previous two cells · 13 + 8 = 21.

Add the previous two cells · 21 + 13 = 34.

Add the previous two cells · 34 + 21 = 55. The last cell is filled.

Done · the answer is 55. Every cell was computed exactly once — plain recursion would recount the same values endlessly.

dp[0]·
dp[1]·
dp[2]·
dp[3]·
dp[4]·
dp[5]·
dp[6]·
dp[7]·
dp[8]·
dp[9]·
dp[10]·
1 / 13

02 Understand It Simply

For Everyone
🔑How It Works

Stores each subproblem's answer the first time it is computed and reads it back instead of solving it again, turning exponential time into linear time.

💡In Plain Words

Stores the answers to small problems in a table and reuses them.

Removing the redundant work of naive recursion cuts O(2^n) to O(n).

📍Where It's Used
  • –Computations with overlapping subproblems
  • –an intro to DP

03 Python Implementation

A clean, readable reference implementation of the core logic of Fibonacci Sequence (DP).

core_implementation.py
def fibonacci(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

04 Frequently Asked Questions

FAQ
What is Fibonacci Sequence (DP)?+

Dynamic programming stores and reuses previously computed subsolutions in a table to eliminate redundant work. It's the classic memoization example, pulling naive recursion from O(2^n) down to O(n).

What is the time complexity of Fibonacci Sequence (DP)?+

The time complexity of Fibonacci Sequence (DP) is O(n). Follow the step-by-step visualization to see exactly why.

Where is Fibonacci Sequence (DP) used?+

Computations with overlapping subproblems, an intro to DP.

What's a simple analogy for Fibonacci Sequence (DP)?+

Stores each subproblem's answer the first time it is computed and reads it back instead of solving it again, turning exponential time into linear time.

→ Dynamic Programming — see allRelated
🧠Longest Increasing Subsequence (LIS)
O(n²)