Memoization (Top-Down DP)

Memoization is the top-down style of dynamic programming. You write the recursive solution naturally, then add a cache so repeated calls return immediately instead of recomputing.

How It Works

The pattern is always the same:

1. Check the cache at the start of the function — if the answer is already stored, return it.
2. Compute the answer recursively.
3. Store the answer in the cache before returning.

function solve(n, memo = new Map()) {
  if (/* base case */) return /* known value */;
  if (memo.has(n)) return memo.get(n);
  const result = /* recurrence using recursive calls */;
  memo.set(n, result);
  return result;
}

Grid Path Counting Example

Count unique paths from the top-left to the bottom-right of an m×n grid, moving only right or down. The state is (row, col) and the recurrence is paths(r, c) = paths(r-1, c) + paths(r, c-1).

function uniquePaths(m, n, memo = new Map()) {
  const key = `${m},${n}`;
  if (m === 1 || n === 1) return 1;          // base case: single row or column
  if (memo.has(key)) return memo.get(key);
  const result = uniquePaths(m - 1, n, memo) + uniquePaths(m, n - 1, memo);
  memo.set(key, result);
  return result;
}

console.log(uniquePaths(3, 7)); // 28

String keys work for multi-dimensional state. For single-integer state, an array index is faster:

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];
}

When Memoization Fits

Memoization can hit JavaScript’s call-stack limit for very deep recursion (n > ~10,000 in most engines). When that matters, tabulation is safer.

Time and Space

For a problem with S unique states, each taking O(w) work, memoization gives O(S * w) time and O(S) space for the cache plus O(depth) for the call stack.

Up Next

See how the same problems can be solved iteratively with a table, avoiding recursion overhead entirely.