Memoization is the top-down approach to Dynamic Programming. Instead of building the answer from scratch, you write a normal recursive function and just add a cache. Every time you solve a subproblem, you save the result. Next time you need it, grab it from the cache instead of recomputing.
Think of it like a student who writes down answers to practice problems in a notebook. When the same problem shows up on the exam, they just flip to the right page. No need to redo the work.
Fibonacci with Memoization
The naive Fibonacci function calls itself exponentially. For fib(10), it computes fib(3) a whopping 21 times. With memoization, each value is computed exactly once.
function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n];
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
console.log(fib(10));
console.log(fib(50));The only change is the memo object. Before computing anything, we check if it is already there. After computing, we store it. The function signature stays the same as the naive version, which makes memoization easy to add to existing code.
Time Complexity Improvement
The naive recursive Fibonacci runs in O(2^n) time — brutal. With memoization, each subproblem is solved once, giving us O(n) time. The space is also O(n) for the cache and recursion stack.
That is the power of memoization. You take a brute force solution that would take thousands of years for large inputs and turn it into something that runs in milliseconds. Same logic, just smarter about what you remember.
When to Use Top-Down
Memoization is great when you do not know which subproblems you will need ahead of time. The recursion naturally explores only the subproblems that matter. It is also easy to convert a working recursive solution — just add the cache and you are done.
The downside is the recursion stack. For very deep problems, you might hit stack overflow. In those cases, the bottom-up tabulation approach we will cover next is often a better choice.