Grid DP
Fill a table shaped like a grid, where each cell's answer comes from the cells above it and to its left.
O(rows × cols)Space O(rows × cols)8 practice problemsStep-through pictureThe idea
Grid DP solves questions about moving through a grid, such as "what is the cheapest route from the top-left to the bottom-right if you can only move right or down?" The DP table has the same shape as the grid. Each cell of the table answers the question for the matching cell of the grid.
Because you only move right or down, the last move into a cell came from the cell above it or the cell to its left. So the answer for a cell is built from those two neighbors. Filling the table row by row, left to right, guarantees both neighbors are ready.
The template finds the smallest total cost of a path, where each grid cell has a cost you pay when you step on it.
An everyday example
Walking through a city of one-way streets
Picture a city laid out in blocks where every street runs only east or south. To find the cheapest way to each corner, you write a number on every corner: the cheapest toll to get there. The toll to any corner is its own toll plus the cheaper of the corner to the north and the corner to the west, because those are the only ways in.
| In the example | In the code |
|---|---|
| The tolls on each corner | The grid of costs |
| Your note on each corner | best[r][c], the cheapest total to reach row r, column c |
| Coming from the north or from the west | best[r - 1][c] or best[r][c - 1] |
| Writing notes street by street | The two nested for loops |
| The note on the last corner | best[rows - 1][cols - 1] |
From the slow way to grid dp
- Start with brute force: list every right-and-down route from the top-left to the bottom-right, add up each route's costs, and keep the smallest. A route through a grid of
rowsbycolscells makesrows - 1moves down andcols - 1moves right, in any order. A 10 by 10 grid has 48,620 routes, and a 20 by 20 grid has 35,345,263,800. - Those routes share almost everything. Thousands of them pass through the same middle cell, and each one adds up the same beginning again. Notice what matters about a route's beginning: only where it ends and what it cost. Once two beginnings reach the same cell, the cheaper one is better for every way of finishing.
- So keep one number per cell:
best[r][c], the cheapest cost of any route from the start to that cell. Because moves only go right or down, the last move into a cell came from the cell above or the cell on the left. Its cheapest cost is the cheaper of those two neighbors, plus its own cost. - The order is easy to get right. Going row by row, left to right, the cell above was filled in the previous row and the cell on the left was filled just before. The top row and left column have only one neighbor each, so they are handled on their own. That double loop is grid DP.
How it works
- Make a table
bestwith the same number of rows and columns asgrid. - The start cell
best[0][0]is justgrid[0][0]: the path that only touches the start. - Cells in the top row can only be reached from the left, so
best[0][c] = best[0][c - 1] + grid[0][c]. - Cells in the left column can only be reached from above, so
best[r][0] = best[r - 1][0] + grid[r][0]. - Every other cell takes the cheaper of above and left, plus its own cost:
Math.min(best[r - 1][c], best[r][c - 1]) + grid[r][c]. - Fill row by row, left to right, and return the bottom-right cell.
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.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function minPathSum(grid) {const rows = grid.length;const cols = grid[0].length;const best = Array.from({ length: rows }, () => new Array(cols).fill(0));for (let r = 0; r < rows; r++) {for (let c = 0; c < cols; c++) {if (r === 0 && c === 0) best[r][c] = grid[0][0];else if (r === 0) best[r][c] = best[r][c - 1] + grid[r][c];else if (c === 0) best[r][c] = best[r - 1][c] + grid[r][c];else best[r][c] = Math.min(best[r - 1][c], best[r][c - 1]) + grid[r][c];}}return best[rows - 1][cols - 1];}
How fast it is
| Time | O(rows × cols) |
|---|---|
| Extra memory | O(rows × cols) |
Every cell is computed once from two neighbors. The table has one number per cell, and it can shrink to one row because each row only reads the row above it.
- Best case
O(rows × cols)Any grid, even one where every cost is 0. Every cell is filled once, whatever the values are.
- Average case
O(rows × cols)Any grid: one comparison and one addition per cell.
- Worst case
O(rows × cols)The same. The costs never change how many cells are read, so there is no slower input.
Common mistakes
- Creating rows with
new Array(rows).fill(new Array(cols)), which puts the same row object in every slot. UseArray.fromwith a function. - Treating the first row and column like the rest and reading
best[-1][c], which throws an error. Handle the edges first. - Allowing moves up or left as well. Then paths can loop, and this table no longer works; you need a shortest-path algorithm such as Dijkstra's.
- Mixing up rows and columns:
grid[r][c]is rowr, columnc. Userfor the outer loop andgrid.lengthfor the number of rows.
When to use it
Look for these clues in a problem:
- The input is a 2-D grid and you move in limited directions, usually right and down.
- The question asks for the cheapest path, the best total, or the number of different paths.
- Some cells are blocked or have costs, and you need the best way around them.
- Breadth-first search would not work because each cell has a cost, but movement only goes one way, so there are no loops.
Check yourself
Answer each one in your head first, then open it.
Why is the top row filled with a running sum?
A cell on the top row can only be reached from the left, so its cheapest route is the one straight along the top. There is no other choice to compare.
What would break if moves could also go left?
A cell could then depend on a cell to its right, which is filled later, and routes could loop. The fill order stops working, and you need a shortest-path algorithm instead.
In the trace, why is best[2][1] only 8 when best[2][0] is 12?
Because the route can come from above instead. best[1][1] is 6, and 6 + 2 = 8 beats 12 + 2 = 14.
How many cells does the code fill for a 300 by 400 grid?
All 120,000 of them, once each, whatever the costs are.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingeasy
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
The table keeps one promise: when the loops reach cell (r, c), every cell above it, and every cell to its left in the same row, already holds the cheapest cost of a route from the start to that cell. Row-by-row order is what makes this true, since those are exactly the cells filled earlier.
Filling the cell keeps the promise. Every route into (r, c) ends with a move from above or from the left. Take a cheapest route and suppose its last move came from above. The part before that move is a route to the cell above, and it must be a cheapest one: if a cheaper one existed, you could swap it in and get a cheaper route to (r, c). So the answer is best[r - 1][c] + grid[r][c] or best[r][c - 1] + grid[r][c], and taking the smaller is right.
This only works because routes can't go back up or left. Then no cell's answer depends on a cell filled later, and no route can loop. The loops visit every cell once and stop, and the promise at the last cell says best[rows - 1][cols - 1] is the cheapest whole route.
Going deeper
3 more ideas
What each cell of the table means
best[r][c] is the smallest total cost of any right-and-down path from the top-left cell to cell (r, c), counting the costs of both ends. It is not the cost of the cell itself; it is the cost of the cheapest whole route that ends there.
How much work it does
Each of the rows * cols cells is filled once with one comparison and one addition, so the time is O(rows * cols). The table is the same size. Each row only reads the row above, so one row of cols numbers is enough if you overwrite it in place.
Counting paths instead
To count paths, replace Math.min(...) + grid[r][c] with a sum: best[r][c] = best[r - 1][c] + best[r][c - 1]. A blocked cell gets 0, because no path can end there. The structure of the loops stays the same.
Work it by hand
Every step in a table, with why
Find the cheapest right-and-down route through a grid with 3 rows and 4 columns. Each row of the trace fills one cell of best.
grid = [[1, 5, 2, 8], [4, 1, 3, 1], [7, 2, 6, 2]]
| Step | (r, c) | grid[r][c] | Above | Left | best[r][c] | What happens | Why |
|---|---|---|---|---|---|---|---|
| 1 | (0, 0) | 1 | - | - | 1 | Start cell | Line 7: the route that only touches the start costs grid[0][0]. |
| 2 | (0, 1) | 5 | - | 1 | 6 | Top row: left only | Line 8: on the top row, the only way in is from the left. |
| 3 | (0, 2) | 2 | - | 6 | 8 | Top row: left only | The top row is a running sum of the costs so far. |
| 4 | (0, 3) | 8 | - | 8 | 16 | Top row: left only | The first row is done. |
| 5 | (1, 0) | 4 | 1 | - | 5 | Left column: above only | Line 9: on the left column, the only way in is from above. |
| 6 | (1, 1) | 1 | 6 | 5 | 6 | Left is cheaper: 5 + 1 | Line 10: coming down the left side and then right beats going across the top. |
| 7 | (1, 2) | 3 | 8 | 6 | 9 | Left is cheaper: 6 + 3 | The route through (1, 1) keeps winning. |
| 8 | (1, 3) | 1 | 16 | 9 | 10 | Left is cheaper: 9 + 1 | The 8 in the top-right corner makes the top route expensive. |
| 9 | (2, 0) | 7 | 5 | - | 12 | Left column: above only | The left column keeps adding: 5 + 7. |
| 10 | (2, 1) | 2 | 6 | 12 | 8 | Above is cheaper: 6 + 2 | Coming down from (1, 1) is much cheaper than the left column. |
| 11 | (2, 2) | 6 | 9 | 8 | 14 | Left is cheaper: 8 + 6 | Both neighbors are close, but 8 is smaller. |
| 12 | (2, 3) | 2 | 10 | 14 | 12 | Above is cheaper; done | The last cell takes the route down the right edge. The loops end and line 13 returns it. |
It returns 12, for the route down, right, right, right, down: 1 + 4 + 1 + 3 + 1 + 2. Both loops end after the bottom-right cell, the last one in the fill order.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Grid DP | O(rows × cols) | O(rows × cols) | Moves only go right and down (or in any set of directions that can't loop), and you may want to rebuild the route. |
| Grid DP with one row | O(rows × cols) | O(cols) | You only need the final cost, and the grid is large. |
| Dijkstra's algorithm | O(n log n) | O(n) | Moves can go in all four directions, so routes can loop back. Here n is the number of cells; costs must not be negative. |
| Try every route | O(2^n) | O(n) | Only to check answers on grids of 4 by 4 or smaller. |
Extra memory: O(rows × cols) for best. Each row only reads the row above, so one array of cols numbers, updated in place from left to right, is enough: O(cols).
How the steps grow
- Grid DP, Grid DP with one row
O(rows × cols) - Dijkstra's algorithm
O(n log n) - Try every route
O(2^n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Grid DP | 100 | 1 million | 1 trillion |
| Grid DP with one row | 100 | 1 million | 1 trillion |
| Dijkstra's algorithm | 33 | 9,966 | 20 million |
| Try every route | 1,024 | more than a quadrillion | more than a quadrillion |
Inputs that need care
5 tricky inputs
- A 1 by 1 grid:
[[7]] - Only the start cell is filled, and it returns 7.
- A single row:
[[3, 1, 4]] - Every cell uses the top-row rule, so it returns the full sum, 8. There is only one route.
- An empty grid:
[] - Line 3 reads
grid[0].lengthand throws aTypeError, becausegrid[0]isundefined. Check for an empty grid first and decide what to return. - Zero or negative costs
- They work as they are. Since moves only go right or down, no route can loop to collect a negative cost twice.
- Rows of different lengths
colscomes from the first row, so a shorter row givesundefinedcosts andNaNtotals. Check that every row has the same length.
Variations and follow-ups
Twists interviewers add
Counting routes, with blocked cells
Store counts and add the two neighbors instead of taking the minimum. A blocked cell gets 0, so nothing passes through it. On the top row and left column, one block cuts off every cell after it.
Collecting the most
To collect the most points instead of paying the least, use Math.max. Everything else is the same, because the argument about the last move doesn't care whether you minimize or maximize.
More kinds of moves
If diagonal moves down and to the right are also allowed, each cell reads three neighbors: above, left, and above-left. Any set of moves works as long as every move goes to a cell later in the fill order.
Two walkers at once
When two people walk from the top-left at the same time and a cell's points can only be collected once, the state becomes (step, r1, r2): both have made the same number of moves, so their columns follow from their rows. This is a 3-D table.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from "start at the top-left, reach the bottom-right, move only right or down", and a request for a count, a cheapest cost, or a best score. A grid with one-way moves is a grid DP.
- Say the meaning of one cell out loud: "
best[r][c]is the cheapest route from the start to here, counting both ends". Then say why the last move came from above or left. - Before running it, check the edges: a 1 by 1 grid, a single row, and a single column. Off-by-one bugs in the first row and column are the most common mistakes.
- Expect "can you use less memory?". Keep one row:
row[c] = Math.min(row[c], row[c - 1]) + grid[r][c], whererow[c]still holds the value from the row above before you overwrite it.
Where frontend code uses it
The same idea in real UI code
- Content-aware image resizing (seam carving) finds the cheapest top-to-bottom line of pixels to remove with grid DP, and it can run in the browser on a canvas.
- Diff views draw an "edit graph": a grid of old lines against new lines where the cheapest path from corner to corner is the diff.
- Puzzle and board games built with canvas or CSS grid count or score routes across the board with this table.