DSAverse

Dynamic Programming

Loading Dynamic Programming...

DP Table Filling

subproblems

O(2^n)→O(n)

Back to Dynamic Programming

Fibonacci Numbers Visualizer

Watch how memoization eliminates redundant calls in the Fibonacci recursion tree, transforming O(2ⁿ) into O(n).

With memo: O(n)

Without memo: O(2ⁿ)

Space: O(n)

Top-down DP

Calculate Fibonacci of: 6

F(3)F(12)

Animation Speed: 1000ms

Fast (300ms)Slow (2000ms)

Progress: Step 1 of 0Phase: start

Fibonacci Sequence

F(0)

F(1)

F(2)

F(3)

F(4)

F(5)

F(6)

Recursion Stack

Call stack is empty

Memoization Cache

memo[0]

—

memo[1]

—

memo[2]

—

memo[3]

—

memo[4]

—

memo[5]

—

memo[6]

—

Current Step

Click Play to begin

Algorithm Details

With Memo:O(n)

Without Memo:O(2ⁿ)

Space:O(n)

Type:Top-down DP

Memoization Benefits

Eliminates redundant calculations
Transforms exponential to linear time
Preserves natural recursive structure
Trade-off: uses O(n) extra space

Knowledge Check

Question 1 of 3