Top-Down

Overview

Memoization is a Top-Down Dynamic Programming technique. You start at the massive final problem (like `fib(50)`), write a standard recursive function, and just before returning an answer, you save it in a cache (like an array or HashMap). On future recursive calls, you check the cache first. It is highly intuitive because you just write normal recursion and add a 2-line cache check.

Syntax

It solves the problem naturally from top to bottom, only calculating branches exactly once.

Top-Down Recursion with Cache

java

public int fib(int n, Integer[] cache) {
    if (n <= 1) return n;
    
    // Check Cache!
    if (cache[n] != null) {
        return cache[n];
    }
    
    // Calculate and Save to Cache
    int result = fib(n - 1, cache) + fib(n - 2, cache);
    cache[n] = result;
    
    return result;
}

Common Pitfalls

Memoization still uses the Call Stack. Even though it is O(N) time, a depth of 100,000 will still cause a Stack Overflow Error.

Interview Tips

Top-Down (Memoization) is often much easier to write during an interview than Bottom-Up (Tabulation) because the recursive logic is more intuitive.

Real-World Example

Any heavy backend API request can be memoized using Redis. If a user asks for complex data, calculate it, save it in Redis, and return it instantly next time.

example

java

// Caching API responses is real-world Memoization.

Take Java Quiz