Visualizers

Fibonacci DP Visualizer

Animate recursion vs memoization vs tabulation for Fibonacci.

native Client-side

Value of N (2-20)

Approach

Speed

DP Table (dp[0] to dp[N])

Ready to compute.

Execution Log

Result F(N): -

Operations (Calls): 0

Current Action:

Idle

Legend:

Uncomputed

Active Lookups (N-1, N-2)

Calculated Value

Fibonacci via Dynamic Programming

The Fibonacci sequence is defined by $F(0) = 0, F(1) = 1$, and $F(n) = F(n-1) + F(n-2)$ for $n \ge 2$. Computing this recursively yields $O(2^n)$ exponential complexity due to overlapping subproblems.

Tabulation (Bottom-Up) vs Recursion

By caching or building results sequentially, we reduce complexity to linear $O(n)$:

DP Tabulation: Solves from base cases up. It builds an array of size $N+1$ and populates `dp[i] = dp[i-1] + dp[i-2]`, using previously solved states.
Standard Recursion: Top-down without cache. Computes `F(5)` by branching into `F(4)` and `F(3)`, recalculating states multiple times.

Implementation

// DP Tabulation (Bottom-Up)
function fibTabulation(n) {
  if (n <= 1) return n;
  const dp = Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

// DP Memoization (Top-Down)
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

# DP Tabulation (Bottom-Up)
def fib_tabulation(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]

# DP Memoization (Top-Down)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

public class FibonacciDP {
    // DP Tabulation (Bottom-Up)
    public static int fibTabulation(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // DP Memoization (Top-Down)
    public static int fibMemo(int n, int[] memo) {
        if (memo[n] != 0) return memo[n];
        if (n <= 1) return n;
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }
}

#include <vector>

// DP Tabulation (Bottom-Up)
int fibTabulation(int n) {
    if (n <= 1) return n;
    std::vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// DP Memoization (Top-Down)
int fibMemo(int n, std::vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.