Dynamic Programming: Fibonacci Visualizer

This visualization demonstrates the Fibonacci sequence calculation using dynamic programming. Compare the recursive approach (with exponential time complexity) with the DP approach (with linear time complexity).

Enter a value n and click "Calculate Fibonacci" to begin

Dynamic Programming Table

Recursion Tree

How Dynamic Programming Works

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations.

function fibonacci(n) {
if (n <= 1) return n;
// Create a DP table to store Fibonacci numbers
let dp = [0, 1];
// Build the table from the bottom up
for (let i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
Naive Recursion
Time: O(2ⁿ)
Space: O(n)
DP Approach
Time: O(n)
Space: O(n)
Optimized DP
Time: O(n)
Space: O(1)