Memoization (Top-Down)

Concept

Memoization (Top-Down DP) is the easiest way to solve a Dynamic Programming problem because it perfectly preserves the intuitive logic of standard Recursion.

The word “Memoization” comes from “memorandum” (to remember).
You literally just take your slow, naive recursive function, and wrap it in a caching layer.

The Mechanism

Let’s optimize the catastrophic $O(2^N)$ Fibonacci function using Memoization.

// Time Complexity: O(N) (We calculate each number exactly once)
// Space Complexity: O(N) (For the Cache AND the Call Stack)

function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
    // 1. Check the Cache first! Have we already solved this?
    if (memo.has(n)) {
        return memo.get(n)!; // Instant O(1) return!
    }

    // 2. Base Cases
    if (n === 0) return 0;
    if (n === 1) return 1;

    // 3. Recursive Step (We MUST save it to a variable, don't just return it)
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);

    // 4. Save to the Cache before returning!
    memo.set(n, result);

    return result;
}

How the Cache prunes the Tree

When fibMemo(5) runs:

1. It calls fibMemo(4).
2. fibMemo(4) calls fibMemo(3) -> fibMemo(2) -> fibMemo(1).
3. The left side of the tree fully executes, doing the heavy math. The results are pushed into the Hash Map.
4. fibMemo(4) finishes.
5. Now fibMemo(5) calls its right child: fibMemo(3).
6. fibMemo(3) checks the Cache. memo.has(3) is TRUE!
7. It instantly returns the cached value. The entire massive recursive tree that normally spawns under fibMemo(3) is completely skipped.

This prunes an exponential $O(2^N)$ branching tree down into a single $O(N)$ straight line of calculations.

Multi-Variable States

In Fibonacci, the state is just a single integer n. We use n as the key in our Hash Map.
But what if your recursive function has two parameters? solve(index: number, remainingCapacity: number)

You cannot use a Map with a single number key. You must combine both parameters into a unique string to use as the cache key.

function solve(i: number, cap: number, memo: Map<string, number>) {
    // Combine the parameters into a unique key!
    const key = `${i},${cap}`;
    
    if (memo.has(key)) return memo.get(key)!;

    // ... math ...
    memo.set(key, result);
    return result;
}

Note: String concatenation inside a heavy recursive loop can be slow in JS. Alternatively, you can use a 2D Array memo[i][cap] initialized with undefined for much faster memory access.

Interview Questions

Q: When should I use Memoization instead of Tabulation?
A: Memoization is vastly superior when the State Space is massive, but you don’t actually need to visit every single state to find the answer. Memoization is “Lazy”—it only physically calculates the specific nodes the recursive tree happens to touch. Tabulation (Bottom-Up) is forced to loop through and calculate every single index from 0 to N, even if the final answer didn’t mathematically require half of them.

Q: Can Memoization cause a Stack Overflow?
A: Yes! Because Memoization is fundamentally a recursive algorithm, it still relies entirely on the Call Stack. If the depth of the recursive tree exceeds ~10,000 frames (e.g., fibMemo(50000)), V8 will throw a Stack Overflow error before the cache can even help. Tabulation (which uses for loops) is completely immune to Stack Overflows.