Grid DP

Count paths, find the cheapest route, or measure shapes on a 2D grid by giving every cell an answer built from the cells next to it.

Overview

A cell reads its neighbors

In a grid DP the state is a cell. dp[r][c] is the answer for cell (r, c): how many paths reach it, the cheapest way to reach it, or the size of a shape that ends there. When moves go only down and right, a cell can be entered from exactly two cells, the one above and the one to the left. So dp[r][c] is some function of dp[r-1][c] and dp[r][c-1], and the problem decides the function.

Unique Paths — number of paths into the cell — add
Minimum Path Sum — cheapest total to reach the cell — min, plus the cell's own cost
Maximum path value — best total to reach the cell — max, plus the cell's own value
Count Square Submatrices — side of the largest all-ones square ending here — min of three neighbors, plus 1

The first row and the first column have only one neighbor, so they are the base cases. A grid of m rows and n columns has mn cells, each costing O(1), so the time is O(mn). A cell reads only the row above and the cell just filled, so one row of length n is enough: O(n) space.

Unique Paths, with an obstacle

Count the paths from the top-left corner to the bottom-right corner moving only down or right. A path arrives at a cell by a down move (counted in the cell above) or by a right move (counted in the cell to the left), and never both, so the two counts add. A cell with an obstacle gets 0: no path continues through it, including the paths along the first row and column past it.

The rows fill top to bottom. Each row reads only the row above, so the table below is also the one-row version: the row is overwritten in place, left to right.

1 — 1 1 1 1 — Only right moves reach the first row
2 — 1 0 1 2 — The wall is 0; the cell after it only inherits from above
3 — 1 1 2 4 — The last cell adds 2 from above and 2 from the left

Without obstacles there is a closed formula: a path of (m - 1) down moves and (n - 1) right moves is fixed by choosing which moves go down, so the count is C(m + n - 2, m - 1). For 3 by 4 that is C(5, 2) = 10 and for 4 by 5 it is C(7, 3) = 35. The formula is a good sanity check on the DP.

Minimum Path Sum, traced

Every cell has a cost, and the total of a path is the sum of the cells it visits. dp[r][c] is the cheapest total to reach the cell: its own cost plus the smaller of the cell above and the cell to the left. Here is the grid and its table.

1 — 3 — 1 — 1 — 4 — 5
2 — 8 — 1 — 3 — 11 — 6
9 — 4 — 1 — 12 — 15 — 7

The answer is 7 along the top row and down the right column. A greedy walk that always steps to the cheaper neighbor takes 1, 2, 8, 1, 1 for 13, because the cheap first step leads into an expensive middle. That is why the problem needs DP: the best route to the end need not start with the best single step, but it must reach some cell on the way by a best route. If the grid may be modified, the table can overwrite the grid itself for O(1) extra space.

Choosing the fill direction: Triangle and Dungeon Game

Not every grid fills from the top-left. Pick the direction so that the answer lands in one cell and the base cases are the simplest edge.

In Triangle, each row has one more number than the row above, and a step goes from index j to index j or j + 1 in the next row. Filling from the bottom row upward, dp[j] becomes the cheapest total from that cell down, and the answer is the single top cell. There are no edge cases, because every cell has both children.

3 6 4 (bottom) — 3 6 4
5 2 — 5 + min(3, 6) = 8, 2 + min(6, 4) = 6
1 (top) — 1 + min(8, 6) = 7

The Dungeon Game runs the same way for a different reason. A knight walks from the top-left to the bottom-right through rooms that add or remove health, and must never reach 0. The question is the least starting health that survives. The forward direction fails because the health needed at a cell depends on the rooms still ahead. Filling from the end, dp[r][c] is the least health needed on entering the cell: the smaller of the two next cells' needs, minus the room's value, and never below 1.

-3 — 5 — 4 — 1
1 — -4 — 4 — 5

The answer is the top-left cell, 4. Reading the bottom-right room: it costs 4, and the knight must end with at least 1, so it needs 5 on entry. The room of 5 above it is a gain, so entering it with 1 is enough.

Squares that end at a cell

Count Square Submatrices with All Ones asks how many square blocks of ones a binary grid contains. dp[r][c] is the side of the largest all-ones square whose bottom-right corner is this cell. A square of side k ending here needs squares of side k - 1 ending at the cell above, the cell to the left and the diagonal cell, so dp[r][c] is 1 plus the smallest of those three, or 0 when the cell is 0. The count of squares ending at a cell equals its dp value (sides 1 up to dp), so the answer is the sum of the whole table.

1 — 0 — 1 — 1 — 0 — 1
1 — 1 — 1 — 1 — 1 — 1
1 — 1 — 1 — 1 — 2 — 2

The sum is 10: eight 1 by 1 squares and two 2 by 2 squares. The same table answers Maximal Square: the largest value squared is the largest area.

Rolling rows and in-place tables

Most grid problems read only the row above, so the space choice is about what you are allowed to destroy.

Full table — O(mn) — You need to rebuild the path afterward
Two rows — O(n) — The recurrence reads only the row above
One row, updated in place — O(n) — dp[c] reads the old dp[c] (above) and the new dp[c-1] (left), so left-to-right order is correct
Overwrite the input grid — O(1) — Modifying the input is allowed

When the grid is a graph: Longest Increasing Path

Some grid problems allow all four directions, and then there is no row order that makes the neighbors ready. Longest Increasing Path in a Matrix asks for the longest path along which values strictly increase. Because values must increase, the path can never revisit a cell, so the moves form a graph with no cycles. A depth-first search with memoization works: the longest path from a cell is 1 plus the longest path from any larger neighbor, and each cell is computed once.

9 — 9 — 4 — 1 — 1 — 2
6 — 6 — 8 — 2 — 2 — 1
2 — 1 — 1 — 3 — 4 — 2

The answer is 4, starting at the 1 in the bottom row: 1, 2, 6, 9. The same idea done without recursion is a topological order: peel the cells with no larger neighbor first, layer by layer, or sort the cells by value and process them from the largest down (the sort adds a log factor). The memoized search and the peeling are O(mn): each cell once, with four neighbor checks.

Two problems on this list that are not grids

Two problems often filed under grid DP use a 2D table that is not a grid of the input.

Burst Balloons is interval DP. Bursting a balloon pays the product of its value and its two current neighbors, and the neighbors change as balloons go. Choosing the first balloon to burst makes the rest depend on the outside. Choosing the last balloon in a range does not: when balloon k is the last one left between the boundaries l and r, its neighbors are exactly l and r, and the two sides were solved independently. dp[l][r] is the most coins from bursting everything strictly between l and r, with a 1 padded on each end.

(0, 2), only the 3 — 3, worth 1 × 3 × 1 — 3
(1, 3), only the 1 — 1, worth 3 × 1 × 5 — 15
(2, 4), only the 5 — 5, worth 1 × 5 × 1 — 5
(0, 3), the 3 and the 1 — last 3: 0 + 15 + 1 × 3 × 5 — 30
(1, 4), the 1 and the 5 — last 5: 15 + 0 + 3 × 5 × 1 — 30
(0, 4), everything — last 5: 30 + 0 + 1 × 5 × 1 (last 3 gives only 0 + 30 + 1 × 3 × 1 = 33) — 35

Ranges are filled shortest first, and each cell tries every k inside it, so the time is O(n³).

Maximum Profit in Job Scheduling is a 1D DP over jobs sorted by end time. dp[i] is the best profit using the first i jobs. Job i is either skipped (dp[i-1]) or taken, in which case add its profit to dp[k], where k is the number of jobs that end no later than this job starts. Binary search finds k in O(log n), so the whole thing is O(n log n).

(1, 3, 50) — 0 — 50
(2, 4, 10) — 0 — max(50, 0 + 10) = 50
(3, 5, 40) — 1 — max(50, 50 + 40) = 90
(3, 6, 70) — 1 — max(90, 50 + 70) = 120

What you will be able to do

Define dp[r][c] for a cell and say which neighbors it reads.
Fill a small grid by hand for paths, costs and squares.
Choose the fill direction, forward or from the end, and explain why.
Cut the table to one row, or reuse the input grid, and say what that gives up.
Recognize a 2D table that is really interval DP or a sorted 1D DP.

When to use it

Count the paths from one corner of a grid to the other with limited moves
Find the cheapest or most valuable path through a grid of costs
A triangle or staircase of numbers where each row feeds the next
A grid with blocked cells, where blocked cells contribute nothing
Measure shapes in a binary grid: the largest square, or how many squares
A cell's answer depends on what comes after it, so the table fills from the end
Any 2D layout where movement is restricted to a few directions

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio