juniorDynamic Programming

Explain the Fibonacci sequence using DP.

Updated Apr 28, 2026

Short answer

The Fibonacci sequence can be solved using Dynamic Programming by storing previously calculated Fibonacci numbers instead of recomputing them. The DP state is usually defined as dp[i], where dp[i] represents the i-th Fibonacci number. This reduces the time complexity from the naive recursive approach's O(2^n) to O(n).

Deep explanation

The Fibonacci sequence follows this mathematical rule:

TEXT
F(0) = 0
F(1) = 1


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

A naive recursive solution directly follows this formula:

Python
def fibonacci(n):
    if n <= 1:
        return n


    return fibonacci(n - 1) + fibonacci(n - 2)

The problem is that the same values are calculated many times.

For example:

TEXT
fibonacci(5)


needs:
fibonacci(4)
fibonacci(3)


fibonacci(4) needs:
fibonacci(3)
fibonacci(2)

The value of fibonacci(3) is calculated repeatedly.

Dynamic Programming solves this by storing results after calculating them once.

DP State Definition

The first step is defining the state:

TEXT
dp[i] = the i-th Fibonacci number

Each index stores a solved subproblem:

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

The transition is:

TEXT
dp[i] = dp[i - 1] + dp[i - 2]

Bottom-Up DP (Tabulation)

The bottom-up approach starts from the base cases and builds the answer step by step.

Implementation:

Python
def fibonacci(n):
    if n <= 1:
        return n


    dp = [0] * (n + 1)


    dp[0] = 0
    dp[1] = 1


    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]


    return dp[n]

Example:

Python
print(fibonacci(7))

The DP table is built as:

TEXT
Index:  0  1  2  3  4  5  6  7
Value:  0  1  1  2  3  5  8 13

The answer is:

TEXT
F(7) = 13

Complexity Analysis

For the full DP table solution:

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

Why?

  • The loop calculates each Fibonacci number exactly once.
  • The array stores n + 1 Fibonacci values.

Space Optimized DP

Notice that to calculate the next Fibonacci number, we only need the previous two values:

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

We do not need the entire DP array.

Optimized implementation:

Python
def fibonacci(n):
    if n <= 1:
        return n


    previous = 0
    current = 1


    for _ in range(2, n + 1):
        previous, current = current, previous + current


    return current

Complexity:

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

Top-Down DP (Memoization)

Another approach is to keep the recursive structure but store already computed results.

Python
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]


    if n <= 1:
        return n


    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)


    return memo[n]

The memo prevents repeated calculations.

Complexity:

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

Why Fibonacci Is a DP Problem

Fibonacci has two important properties that make it suitable for Dynamic Programming:

  1. Overlapping subproblems

The same smaller Fibonacci values are needed multiple times.

Example:

``text id="y6q2rx" fibonacci(5) and fibonacci(4) both require fibonacci(3) ``

  1. Optimal substructure

The solution to a larger problem can be built from solutions to smaller problems.

Example:

``text id="u3m8kw" F(5) = F(4) + F(3) ``

Real-world example

Suppose a system needs to generate Fibonacci values for a mathematical visualization tool.

Using DP:

Python
def generate_fibonacci(n):
    if n <= 0:
        return []


    if n == 1:
        return [0]


    dp = [0, 1]


    for i in range(2, n):
        dp.append(dp[i - 1] + dp[i - 2])


    return dp




print(generate_fibonacci(10))

Output:

TEXT
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

The program calculates each value once and reuses previously computed results.

Common mistakes

  • * Implementing naive recursion and calling it a DP solution.
  • * Forgetting to define what `dp[i]` represents.
  • * Initializing incorrect base cases such as `dp[0] = 1`.
  • * Using a DP array when only two previous values are needed.
  • * Confusing memoization with tabulation.
  • * Forgetting that DP works by storing results of overlapping subproblems.
  • * Ignoring edge cases like `n = 0` and `n = 1`.

Follow-up questions

  • Why does Dynamic Programming improve Fibonacci performance?
  • What is the DP state for Fibonacci?
  • What is the difference between memoization and tabulation for Fibonacci?
  • Why can Fibonacci DP use O(1) space?
  • Does Fibonacci always require Dynamic Programming?
  • What are the two properties that make Fibonacci suitable for DP?

More Dynamic Programming interview questions

View all →