Grid path DP

43 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

A 3×3 grid of tolls:

Start at the top-left, finish at the bottom-right, moving only right or down, paying each cell you enter. What is the cheapest route? By hand you list the routes: right, right, down, down costs 1 + 3 + 1 + 1 + 1 = 7; down, down, right, right costs 1 + 1 + 4 + 2 + 1 = 9; and so on. Six routes here, and 7 is the best.

How many routes in general? Each route is a sequence of 2 rights and 2 downs in some order, and for an m×n grid the count is the binomial number of ways to arrange the moves. A 20×20 grid has about 35 billion routes. Listing them is out.

Build the structure, one piece at a time

Piece one: a second grid, dp, the same size, where dp[r][c] will hold the cheapest cost to reach cell (r, c).

Piece two: the observation. A cell can only be entered from the cell above or the cell to its left, because moves are right or down. So the cheapest way to reach it is its own toll plus the cheaper of those two neighbours' best costs:

dp[r][c] = grid[r][c] + min( dp[r − 1][c], dp[r][c − 1] )

Piece three: fill the first row and first column, which have only one way in, then fill the rest row by row so that the two neighbours are always ready.

The bottom-right entry is 7. If the question were "how many routes" instead of "cheapest route", the same table works with addition in place of min and 1 in place of the toll.

Why it is correct

The invariant: every filled dp entry is the true cheapest cost to that cell. The top-left is right by definition. Edge cells have one way in, so their cost is the previous cell's cost plus their toll. Any other cell is entered last from above or from the left, so the cheapest route to it is the cheapest route to one of those two neighbours followed by one step, and the formula takes the better of the two correct neighbour values. Filling row by row guarantees both neighbours are computed before they are needed.

Why it is fast

One min and one addition per cell:

work = m · n, 400 steps for 20×20 instead of 35 billion routes

Memory can shrink to one row, since a row needs only the row above and the entry just filled.

How to recognise it in an interview

Cues: "move only right or down", "number of paths", "minimum path sum", "triangle", "falling path", any grid where a cell's answer depends on a fixed set of earlier cells. The first thing to say: "each cell is reached from a constant number of neighbours, so I fill a table in an order where those neighbours come first." Minimum Path Sum is the example above. Unique Paths is the counting version with dp = up + left. Unique Paths II adds obstacles, whose entries are set to 0 so no route passes through them.

02The idea in one line

dp[r][c] from the cell above and the cell to the left.

Reach for it when: Unique paths I/II, min path sum, triangle, falling path, dungeon game.

Cost: O(mn) time.

03The walk-through, step by step

The video works one example: Minimum Path Sum on [[1,3,1],[1,5,1],[4,2,1]]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Only right and down moves: a cell is reached from above or from the left
2. Start: dp[0][0] = 1
3. dp[0][1] = 3 + 1 = 4 (one way in)
4. dp[0][2] = 1 + 4 = 5 (one way in)
5. dp[1][0] = 1 + 1 = 2 (one way in)
6. dp[1][1] = 5 + min(4, 2) = 7
7. dp[1][2] = 1 + min(5, 7) = 6
8. dp[2][0] = 4 + 2 = 6 (one way in)
9. dp[2][1] = 2 + min(7, 6) = 8
10. dp[2][2] = 1 + min(6, 8) = 7
11. Bottom-right holds the answer: 7 (1→3→1→1→1)
12. Each cell looks at two neighbours: O(m·n) time, one row of memory if rolled

04Asked at Google

10 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, 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, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).