DYNAMIC PROGRAMMING · FOUNDATION

Memoization (top-down DP)

Write the natural recursive solution, then save each call's answer in a cache so no question is answered twice.

Time O(rows × cols)Space O(rows × cols)10 practice problemsStep-through picture

The idea

Memoization means "writing a memo": when a function finishes a call, it writes the answer down, keyed by the arguments. Next time it is called with the same arguments, it returns the saved answer instead of working it out again.

It turns a slow recursive solution into a fast one. Many recursive solutions ask the same smaller question over and over. With a cache, called the memo, each different question is solved once. Every repeat costs only a lookup.

This is called top-down dynamic programming. You start from the big question at the top and let the recursion go down to the small ones. You only solve the small questions that the big one actually needs.

An everyday example

A help desk with a notebook

A help desk gets the same questions many times a day. The first time someone asks "how do I reset my password", the agent works out the answer and writes it in a notebook. When the next person asks the same thing, the agent reads the notebook instead of working it out again. The notebook is the memo, and each question is a set of arguments.

How the example maps to the code
In the example	In the code
The notebook	`const memo = new Map()`
The exact question asked	The key built from the arguments, `r + "," + c`
Checking the notebook first	`if (memo.has(key)) return memo.get(key)`
Working out a new answer	`paths(r - 1, c) + paths(r, c - 1)`
Writing the answer down	`memo.set(key, result)`

From the slow way to memoization (top-down dp)

Start with the plain recursive solution, because it is the easiest one to get right. To count the right-and-down routes to cell (r, c), add the routes to the cell above and the routes to the cell on the left. Cells in the top row or left column have exactly one route. The code is three lines, and it follows the problem's wording closely.
Then measure it. For a 10 by 10 grid it makes 97,239 calls to find 48,620 routes. For a 16 by 16 grid it makes 310,235,039 calls. The count roughly doubles each time the grid grows by a row and a column, because every call that isn't on an edge makes two more calls.
Look at which calls happen. A 10 by 10 grid has only 100 cells, so there are only 100 different questions. The function asks the same few questions thousands of times. Because the answer for a cell depends only on r and c, every repeat of a question gets the same answer as the first time.
So keep the recursion, but give it a memory. Before doing any work, build a key from the arguments and look it up in a Map called memo. If it is there, return it. If not, compute it, store it, and return it. That cache in front of the recursive function is memoization.

How it works

Write the recursive function first. Here paths(r, c) returns the number of ways to walk from the top-left cell to cell (r, c) moving only right or down.
Write the base case: any cell in the top row or left column (r === 0 || c === 0) can be reached in exactly 1 way.
Build a key from the arguments, such as "2,3", so each different question gets its own entry.
Before doing any work, check the memo. If the key is there, return the saved answer.
Otherwise compute the answer with the recursive calls: paths(r - 1, c) + paths(r, c - 1).
Save the answer with memo.set(key, result) and return it.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function countPaths(rows, cols) {
const memo = new Map();
function paths(r, c) {
if (r === 0 || c === 0) return 1;
const key = r + "," + c;
if (memo.has(key)) return memo.get(key);
const result = paths(r - 1, c) + paths(r, c - 1);
memo.set(key, result);
return result;
}
return paths(rows - 1, cols - 1);
}

How fast it is

Time	`O(rows × cols)`
Extra memory	`O(rows × cols)`

Each cell's question is answered once and every repeat is a map lookup. The memo holds one number per cell, and the call stack can be rows + cols calls deep.

Best caseO(1)
rows or cols is 1. The first call is on an edge and returns 1 right away.
Average caseO(rows × cols)
Any bigger grid. Every cell off the edges gets computed once, since the top call needs all of them.
Worst caseO(rows × cols)
The same as the average: about rows × cols keys, each worked out once with one addition, plus up to two quick lookups per key.

Common mistakes

Saving into the memo but never checking it, or checking it after the recursive calls. The check must come first, before any work.
Building keys that collide, such as r + "" + c, where 1, 12 and 11, 2 both become "112". Put a separator between the parts.
Memoizing a function whose answer depends on something outside its arguments, like a variable that changes during the search. Every input that affects the answer must be part of the key.
Creating the memo inside the recursive function, so each call gets a fresh, empty memo. Create it once, outside.
Recursing 100,000 levels deep and hitting the call stack limit. Use tabulation for very long chains of states.

When to use it

Look for these clues in a problem:

You can already write a recursive solution, but it is far too slow on larger inputs.
The recursive function is called many times with the same arguments.
The function's answer depends only on its arguments, not on anything outside that changes.
Only some of the possible states are actually reached, so filling a whole table would waste work.

Check yourself

Answer each one in your head first, then open it.

Why must the memo check come before the recursive calls?

Because the point is to skip the work. If you check after the calls, every call still recurses fully, and the memo only stores answers that are never used.

In the 3 by 4 trace, which two calls were answered from the memo?

paths(1, 2) while computing paths(2, 2), and paths(1, 1) while computing paths(2, 1). Each was solved earlier in the first half of the run.

What goes wrong if paths also read a global counter that changes?

The saved answers would depend on something the key doesn't include, so a later call could get an answer computed under different conditions. Every input that affects the result must be part of the key.

How deep can the call stack get for a grid with rows rows and cols columns?

About rows + cols - 2 calls, because each call lowers r + c by one until one of them hits 0.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 10 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

#487Focus Routes Across a Widget Grid

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Memoization never changes an answer, and the reason is simple: paths(r, c) depends only on its arguments. It reads no outside variable that changes and has no side effects. So the value saved the first time is exactly the value any later call would compute. A function with this property is called pure, and only pure functions are safe to memoize.

The recursion itself is right because of how routes split. Every route into (r, c) makes its last move from the cell above or from the cell on the left, never both. So the count is the routes into (r - 1, c) plus the routes into (r, c - 1). Edge cells have one route, because only one direction leads into them.

It always ends, because each call lowers r + c by one, and every chain of calls reaches r === 0 or c === 0. It is fast because the memo check comes before any work: each key is computed at most once. A computed call makes two calls, and every other call returns at once, so the total calls are at most one plus twice the number of keys.

Going deeper

3 more ideas

Why the cache makes it fast

Without the memo, paths(r, c) calls two smaller cases, which call two more each, and the number of calls roughly doubles at every level. With the memo, each of the rows * cols different cells is worked out once. Every other call is a quick lookup, so the total work is about rows * cols.

How much work memoization does

The time is the number of different states times the work inside one call. Here that is rows * cols states with one addition each. The memo stores one answer per state, and the recursion can go rows + cols calls deep, which also uses memory.

When recursion gets too deep

JavaScript engines stop with a "Maximum call stack size exceeded" error after roughly ten thousand nested calls, depending on the browser. If the recursion can go that deep, for example a state per item in a list of 100,000 items, switch to tabulation, which uses a loop instead.

Work it by hand

Every step in a table, with why

Count the right-and-down routes through a grid with 3 rows and 4 columns. Each row is one call of paths, or one call finishing.

rows = 3, cols = 4, so the first call is paths(2, 3)

Step	Call	`memo.size`	Result	What happens	Why
1	`paths(2, 3)`	0	waits	Key `"2,3"` is new	Not on an edge and not in the memo, so it needs `paths(1, 3)` and `paths(2, 2)`. It calls `paths(1, 3)` first.
2	`paths(1, 3)`	0	waits	New; `paths(0, 3)` is 1	Its first call, `paths(0, 3)`, is on the top row and returns 1 without touching the memo. Next it needs `paths(1, 2)`.
3	`paths(1, 2)`	0	waits	New; `paths(0, 2)` is 1	The same pattern one column to the left.
4	`paths(1, 1)`	0	waits	New; both parts are edges	`paths(0, 1)` and `paths(1, 0)` are both edge cells, so each returns 1.
5	`paths(1, 1)`	1	2	Saved under `"1,1"`	`1 + 1 = 2`. This is the first answer written into the memo.
6	`paths(1, 2)`	2	3	Saved under `"1,2"`	`1 + 2 = 3`: one route along the top, plus two through cell (1, 1).
7	`paths(1, 3)`	3	4	Saved under `"1,3"`	`1 + 3 = 4`. The first half of the top call is done.
8	`paths(2, 2)`	3	waits	Key `"2,2"` is new	Now the top call asks for its second part, which needs `paths(1, 2)` and `paths(2, 1)`.
9	`paths(1, 2)`	3	3	Memo hit	This question was answered four rows ago. Line 6 returns the saved 3, and no recursion happens below it.
10	`paths(2, 1)`	3	waits	New	It needs `paths(1, 1)` and `paths(2, 0)`.
11	`paths(1, 1)`	3	2	Memo hit	Another repeat, answered by a lookup. Then `paths(2, 0)` is on the left edge and returns 1.
12	`paths(2, 1)`	4	3	Saved under `"2,1"`	`2 + 1 = 3`.
13	`paths(2, 2)`	5	6	Saved under `"2,2"`	`3 + 3 = 6`, built from one memo hit and one new answer.
14	`paths(2, 3)`	6	10	Saved, returned	`4 + 6 = 10`. The top call finishes and line 11 returns it.

It returns 10. The memo ends with 6 answers, one for each cell that is not on an edge, and the whole run makes 13 calls. Without the memo it makes 19; on a 10 by 10 grid the gap is 163 calls against 97,239.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Memoization (top-down DP)	`O(rows × cols)`	`O(rows × cols)`	When the recursive version is the natural way to think about the problem, or when only some states are reachable from the top question.
Plain recursion	`O(2^n)`	`O(n)`	Never for real sizes. It is useful as the first draft that memoization then speeds up.
Tabulation	`O(rows × cols)`	`O(rows × cols)`	When nearly every state is needed or the recursion would be very deep. A loop has no stack limit and less overhead per state.
Counting formula	`O(rows + cols)`	`O(1)`	For this exact grid with no blocks: the answer is the number of ways to choose which `rows - 1` of the `rows + cols - 2` moves go down. It breaks as soon as cells are blocked.

Extra memory: O(rows × cols) for the memo, which holds one number for each cell off the edges, plus O(rows + cols) for the call stack, which can be that many calls deep.

How the steps grow

Memoization (top-down DP), Tabulation O(rows × cols)
Plain recursion O(2^n)
Counting formula O(rows + cols)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Memoization (top-down DP)	100	1 million	1 trillion
Plain recursion	1,024	more than a quadrillion	more than a quadrillion
Tabulation	100	1 million	1 trillion
Counting formula	20	2,000	2 million

Inputs that need care

5 tricky inputs

A grid with one row or one column: countPaths(1, 6): The first call is paths(0, 5), which is on the top row, so it returns 1. That is right: there is only one straight route.
A grid with zero rows: countPaths(0, 3): The first call is paths(-1, 2). r only gets more negative, so it never reaches 0 and the code throws RangeError: Maximum call stack size exceeded. Return 0 for an empty grid before recursing.
A 30 by 30 grid: There are 30,067,266,499,541,040 routes, more than Number.MAX_SAFE_INTEGER, so the answer is slightly wrong. Use BigInt values, or the modulo the problem asks for.
Calling countPaths many times with different sizes: Each call makes a fresh memo, so nothing is shared. Since paths(r, c) doesn't depend on the grid size, you could move the memo outside and reuse it across calls.
A very tall grid, such as 20,000 rows and 2 columns: The recursion goes about 20,000 calls deep, which can pass the engine's stack limit. Use the tabulation version, which fills the same table with a loop.

Variations and follow-ups

Twists interviewers add

Grids with blocked cells

Add one base case before the memo check: a blocked cell returns 0. The edge rule changes too, because a block on the top row cuts off every cell to its right. The memo and the key stay the same.

A general memoize helper

A helper like memoize(fn) returns a wrapper that builds a key from the arguments, checks a Map, and calls fn on a miss. For the recursion to use the cache, the function must call the wrapped version of itself, not the original.

A memo array instead of a Map

When the arguments are small integers, a 2-D array such as memo[r][c] is faster than string keys. Fill it with -1 or undefined to mean "not computed", since 0 can be a real answer in some problems.

Limited caches

In real apps a memo can grow without end. An LRU cache keeps only the most recently used answers, and a WeakMap lets an object key and its answer be garbage collected together. Both trade some repeated work for bounded memory.

In an interview

Spot it, explain it, answer follow-ups

Spot it when you can already write a correct recursive solution and it is too slow. Ask: does the function depend only on its arguments, and do the same arguments come back? If yes, memoize.
Explain it in two sentences: "This recursion repeats the same calls. I'll store each result by its arguments, so each one is computed once." Then say the number of different states, because that is the running time.
Test it by hand on a tiny input where a repeat must happen, like a 3 by 3 grid, and point at the call that is answered from the memo. Also test a grid with one row, which should return 1 without recursing.
Expect the follow-up "what if the input is so big the recursion overflows?". Answer: switch to tabulation, filling the same states in an order where each state's parts come first.

Where frontend code uses it

The same idea in real UI code

React's useMemo and React.memo save a result and reuse it while the inputs stay the same, which is memoization keyed by the dependency list or props.
Selector libraries like Reselect wrap a function so it only recomputes derived state, such as a filtered list, when its inputs change.
Data-fetching caches such as TanStack Query keep each response under a query key, so asking for the same data twice reuses the first result.

Memoization (top-down DP)

The idea

An everyday example

A help desk with a notebook

From the slow way to memoization (top-down dp)

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why the cache makes it fast

How much work memoization does

When recursion gets too deep

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Grids with blocked cells

A general memoize helper

A memo array instead of a Map

Limited caches

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

A help desk with a notebook

From the slow way to memoization (top-down dp)

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why the cache makes it fast

How much work memoization does

When recursion gets too deep

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Grids with blocked cells

A general memoize helper

A memo array instead of a Map

Limited caches

In an interview

Where frontend code uses it

Related algorithms