Dynamic Programming

Fibonacci with Memoization

Turn exponential recursion into linear time by caching subresults.

TimeO(n)SpaceO(n)CategoryDynamic Programming

Visualize this — step by stepNo signup needed.

The naive recursive Fibonacci recomputes the same values exponentially many times. Memoization stores each computed `fib(k)` in a table the first time it is needed, so every subproblem is solved once — collapsing the O(2ⁿ) call tree into O(n).

This is the gateway to dynamic programming: recognizing overlapping subproblems and caching them. Once you see the memo table fill in, the leap from recursion to bottom-up DP becomes natural.

AlgoLens shows the recursion tree and the memo array together — you literally see which calls hit the cache and return instantly instead of recursing.

The code

fibonacci_memoization.cpp

#include <bits/stdc++.h>
using namespace std;

vector<int> memo;

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    int n;
    cin >> n;
    memo.assign(n + 1, -1);
    cout << fib(n) << '\n';
    return 0;
}

Open this in the visualizer

Now run your own Fibonacci with Memoization

AlgoLens traces your code — arrays, graphs, trees and recursion — from a real execution, so you see how it actually behaves, not a canned animation.

Paste your code

Keep going

0/1 Knapsack

Take it or leave it — the DP table that defines the field.

Longest Common Subsequence

How much two strings share, in order — the basis of diff.

Coin Change

Fewest coins for an amount — where greedy fails and DP works.

Bubble Sort

The simplest sort — watch the largest value bubble to the end each pass.