Memoised DFS (top-down)

57 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Here is a 3 × 3 grid of numbers. From any cell you may step up, down, left or right, but only onto a strictly bigger number. How long is the longest such path?

By hand you would start at some cell, say the 1 in the bottom middle, and walk: 1 → 2 → 6 → 9, length 4. Then start at every other cell and walk every possible way. The trouble is that walks share tails. The walk from 1 goes through 2, and the walk from 2 goes through the same 6 and 9 again. Each start explores a tree of choices, and on a 100 × 100 grid the number of walks is astronomically large, even though the answer for "best path starting at this 6" is the same every time you need it.

Build the structure, one piece at a time

Write the question as a function: best(r, c) = length of the longest increasing path that starts at cell (r, c). It has a natural recursive answer: look at the four neighbours, keep the ones with a bigger number, and take 1 plus the best of their answers. A cell with no bigger neighbour has answer 1.

Now add the one new piece: a memo, a second grid the same size, empty at first. Before computing best(r, c), look in the memo; if the cell is filled, return it. After computing, store it. The recursion is unchanged; only the cache is new.

1. Ask the 9 at (0,0). No bigger neighbour. memo[0][0] = 1.
2. Ask the 6 at (1,0). Bigger neighbours: the 9 above. It is cached, so reuse 1 with no recursion. memo[1][0] = 1 + 1 = 2.
3. Ask the 2 at (2,0). Bigger neighbour: the 6 above, cached at 2. memo[2][0] = 3.
4. Ask the 1 at (2,1). Bigger neighbours: 2 (cached, 3), 6 at (1,1) (not yet known), 1 at (2,2) is not bigger. Compute (1,1): its bigger neighbours are the 9 at (0,1) and the 8 at (1,2), both quickly resolved to 1. memo[1][1] = 2. So memo[2][1] = 1 + max(3, 2) = 4.

Filled memo so far, row by row: 1 1 · / 2 2 1 / 3 4 ·. The remaining two cells fill the same way, and the answer is the largest entry, 4, for the path 1 → 2 → 6 → 9.

Why it is correct

The invariant: once a memo cell is filled, it holds the true longest path from that cell. The recursion computes a cell only from its bigger neighbours, and the path "bigger neighbour" relation has no cycles, since numbers strictly increase along it. So when a cell is being computed, every neighbour it asks about is either already final or will be computed by the same rule without ever coming back to this cell. By induction from the cells with no bigger neighbours (answer 1), every stored value is correct, and reusing it instead of recomputing changes nothing.

best(r, c) = 1 + max over bigger neighbours (r′, c′) of best(r′, c′), or 1 if there is none

Why it is fast

Each of the m × n cells is computed exactly once, and computing it looks at 4 neighbours. Every later request is a memo lookup. So the total work is about 4mn steps: O(mn). On a 100 × 100 grid that is 40,000 steps, where the memo-free recursion could take longer than the age of the universe on a grid shaped like a long increasing snake. Memory is one extra grid. In general the cost of memoised recursion is (number of distinct states) × (work per state), and it only helps when the same state is reached many times.

How to recognise it in an interview

Cues: a recursive definition that is easy to write, a state made of a few small numbers (a cell, an index and a remaining budget, a pair of indices), and the feeling that "the same subproblem keeps coming back". Write the recursion first, then add the cache keyed by the state. Longest Increasing Path in a Matrix is the grid above. Target Sum caches on (index, running total). Soup Servings and New 21 Game cache on remaining amounts, and the memo turns an exponential tree into a table.

02The idea in one line

Recurse on the natural subproblem and cache by its parameters.

Reach for it when: Longest increasing path in a matrix, target sum, out of boundary paths, knight probability.

Cost: O(states · transitions) time.

03The walk-through, step by step

The video works one example: Longest Increasing Path on [[9,9,4],[6,6,8],[2,1,1]]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Ask each cell: how long is the best path starting from you? Cache the answer
2. Visit (0,0) = 9: try every bigger neighbour
3. memo[0][0] = 1, cached for good
4. Visit (1,0) = 6: try every bigger neighbour
5. (0,0) is cached: reuse 1, no recursion
6. memo[1][0] = 2, cached for good
7. Visit (2,0) = 2: try every bigger neighbour
8. (1,0) is cached: reuse 2, no recursion
9. memo[2][0] = 3, cached for good
10. Visit (2,1) = 1: try every bigger neighbour
11. Visit (1,1) = 6: try every bigger neighbour
12. Visit (1,2) = 8: try every bigger neighbour
13. memo[1][2] = 1, cached for good
14. Visit (0,1) = 9: try every bigger neighbour
15. memo[0][1] = 1, cached for good
16. memo[1][1] = 2, cached for good
17. memo[2][1] = 4, cached for good
18. The remaining cells fill the same way; the answer is the largest entry: 4 (1→2→6→9)
19. Each cell is solved once and reused: O(m·n) instead of exponential

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).