Memoization

Why memoization matters

Now that we've covered Introduction to Dynamic Programming and the Recursive Approach, you can already express a problem in terms of smaller versions of itself.

The issue is that naive recursion often recomputes the same answers many times. Memoization is the first practical upgrade: remember the result of a subproblem the first time you solve it, then reuse it later.

For a full-stack engineer, this should feel familiar: it is like caching an expensive service response, database query, or build artifact. Same inputs? Reuse the known output.

In this lesson, we'll focus on memoization itself: how to spot it, implement it safely, and avoid common mistakes.

Memoization in one sentence

Memoization stores the output of a function call so the same call can return immediately later.

The contract is:

• Same inputs must always produce the same output.
• The cached value must represent a complete solved subproblem.
• The cache lookup must happen before doing the expensive recursive work.
• The cache write must happen after computing the answer.

A common shape looks like this:

1. Build or receive a memo object/map.
2. Check whether the current subproblem is already stored.
3. If yes, return it.
4. Otherwise, solve recursively.
5. Store and return the result.

This turns repeated work into quick lookups.

Same recursive idea, less waste

In Recursive Approach, naive Fibonacci showed how recursion can explode because fib(3), fib(4), and friends are solved again and again.

Memoization keeps the same recursive definition, but adds a memory layer.

Notice the order:

• Base case first or memo check first can both work here, but base cases are cheap and clear.
• Check memo before expanding recursion.
• Store the computed result before returning.

```javascript
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;

  if (n in memo) {
    return memo[n];
  }

  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fibMemo(10)); // 55
console.log(fibMemo(40)); // 102334155
```

A naive recursive Fibonacci solution recomputes many subproblems. A memoized version stores answers after computing them.

What is the main performance benefit of memoization here?

The key represents the subproblem

The most important design choice is the memo key.

A memo key must uniquely identify everything that can change the answer.

Examples:

• fib(n) → key can be n
• gridPaths(row, col) → key can be row,col
• canSum(target, nums) → key usually needs at least target, and sometimes more depending on whether nums changes

For JavaScript, common memo containers are:

• Plain object: good for simple string/number keys
• Map: better when keys are not simple strings or you want cleaner key handling

Bad keys cause subtle bugs: the function may return a cached answer for a different subproblem.

Memoizing multiple parameters

Let's reuse the grid-paths style problem from Recursive Approach.

Suppose you can only move down or right. How many ways are there to get from the top-left of an m x n grid to the bottom-right?

The subproblem is identified by both dimensions: m and n. So the memo key must include both.

```javascript
function gridPaths(m, n, memo = {}) {
  const key = `${m},${n}`;

  if (key in memo) {
    return memo[key];
  }

  if (m === 1 && n === 1) return 1;
  if (m === 0 || n === 0) return 0;

  memo[key] = gridPaths(m - 1, n, memo) + gridPaths(m, n - 1, memo);
  return memo[key];
}

console.log(gridPaths(3, 3));   // 6
console.log(gridPaths(18, 18)); // 2333606220
```

True or false:

If a recursive function has no repeated subproblems, adding memoization will always improve its asymptotic time complexity.

In memoization, the value used to uniquely identify a subproblem in the cache is called the memo ____.

Watch for these mistakes

Memoization is simple, but the bugs can be sneaky.

1. Forgetting to pass the memo

If each recursive call creates a new memo, nothing is shared. You still recompute work.

2. Using an incomplete key

If the answer depends on (index, remaining) but your key only uses remaining, different states may collide.

3. Caching impure results

Memoization assumes stable outputs. If a function depends on time, random values, external state, or mutating globals, caching can return stale or invalid answers.

4. Mutating cached objects

If you store arrays or objects, be careful. Returning and then mutating a cached reference can corrupt future answers.

In backend terms: cache correctness matters as much as cache speed.

What you now have

Memoization is the bridge from expressive recursion to efficient dynamic programming.

You should now be able to:

• Identify repeated subproblems in a recursive solution
• Add a shared cache to avoid recomputation
• Choose memo keys that fully represent the current state
• Recognize when memoization will not help much
• Avoid common cache correctness bugs

Next, we'll build on this directly with Top-Down Dynamic Programming, where memoized recursion becomes a more formal problem-solving pattern.