Fibonacci Visualizer

Visualize Fibonacci subproblems, memoization, and tabulation to understand repeated work, state reuse, and dynamic programming.

Ready. Use the controls to begin exploring Fibonacci.

Fibonacci Sequence Visualizer

n (0-25):

Speed:

F(0)

F(1)

F(2)

F(3)

F(4)

F(5)

F(6)

F(7)

F(8)

F(9)

F(10)

F(0) = 0 (base case)

Step 1 / 20

Animation Legend

Dependency Read

Newly Computed

Stored Value

Each cell F(i) is computed once using the two previously stored values F(i-1) and F(i-2) (Yellow). The result is then written into the table (Green) so it never needs to be recalculated, turning an exponential recursive approach into a linear-time tabulation.

Java Implementation (Bottom-Up Tabulation)

public int fibonacci(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    if (n >= 1) dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

What is the Fibonacci Sequence DP problem?

The Fibonacci sequence is the classic introduction to Dynamic Programming. Each number is the sum of the two preceding ones: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. A naive recursive solution recomputes the same subproblems repeatedly, leading to exponential time complexity O(2^n).

By storing each computed value in a table (tabulation) instead of recalculating it, we only ever solve each subproblem once. This is the core idea behind Dynamic Programming: trade memory for time by caching overlapping subproblems, similar to the approach used in the Knapsack Problem and Longest Common Subsequence.

Time & Space Complexity

Naive RecursionO(2^n)
DP Tabulation TimeO(n)
DP Tabulation SpaceO(n)
Optimized SpaceO(1)

* Space can be reduced to O(1) by only keeping the last two values instead of the full table.

Why use Dynamic Programming?

✓
Overlapping SubproblemsF(5) and F(4) both depend on F(3), so recomputing it repeatedly wastes work.
✓
Optimal SubstructureThe solution to F(n) is built directly from the solutions to smaller subproblems.
✓
Foundational PatternThe same tabulation technique scales up to far more complex problems like Knapsack and LCS.

Fibonacci Sequence Complete Info Card

Dynamic ProgrammingTabulation

The Fibonacci sequence is built bottom-up by storing each computed value so it never has to be recalculated, turning an exponential recursive approach into a linear-time tabulation.

Algorithm Characteristics

Time Complexity (Naive Recursion)

Recomputes overlapping subproblems repeatedly

O(2^n)

Time Complexity (DP Tabulation)

Each value computed exactly once

O(n)

Space Complexity (Full Table)

Stores every F(i) from 0 to n

O(n)

Space Complexity (Optimized)

Only the last two values are needed

O(1)

Optimal Substructure

F(n) built directly from F(n-1) and F(n-2)

Yes

Overlapping Subproblems

Same F(i) needed by many larger calls

Yes

Tabulation Process Steps

Initialize F(0) = 0 and F(1) = 1

For i from 2 to n, read F(i-1) and F(i-2)

Compute F(i) = F(i-1) + F(i-2)

Store F(i) in the table

Repeat until F(n) is reached

Return F(n) as the final answer

Optimization Techniques

Memoized Recursion

Cache results of recursive calls in a map

if (memo.has(n)) return memo.get(n);

Rolling Variables

Drop the array, keep only the last two values

[prev, curr] = [curr, prev + curr];

When to Use

•Introducing the concept of overlapping subproblems
•Any problem with a simple linear recurrence relation
•Teaching the difference between recursion and tabulation

When to Avoid

•Naive recursion without memoization (exponential blowup)
•Very large n without a closed-form or matrix-exponentiation approach
•When full table history isn't needed (use O(1) space instead)

Did You Know? Fibonacci numbers can also be computed in O(log n) time using matrix exponentiation.

Teaching toolFoundational DPMemoization