DP on Grids (2D)
Quick reference
| Unique Paths / Minimum Path Sum — full table | O(rows × cols) |
| Unique Paths / Minimum Path Sum — rolling row | O(rows × cols) |
DP Fundamentals built a table of answers along one axis: dp[i] depended on dp[i-1] and dp[i-2], a straight line of subproblems. Grid DP is the same "remember what you have already solved" idea, spread across two axes instead of one. dp[i][j] depends on neighboring cells in a grid, not only the one or two entries before it in a line. Nothing conceptually new happens here. The table only grew a second dimension.
Imagine that you fill in a grid of answers cell by cell ("how many ways to get here" or "what is the cheapest path to here"), where each cell needs only the answer already computed in the cell above it and the cell to its left. Fill the grid in reading order, top row to bottom row, and left to right in each row. By the time you reach any cell, everything that it depends on is already there and waiting.
A 2D table, filled in reading order
function solve(grid):
rows, cols = grid dimensions
dp = 2D array, rows x cols
# The base case row and column often follow a SPECIAL rule, not the general recurrence.
seed dp[0][*] and dp[*][0] by hand
for i from 1 to rows - 1:
for j from 1 to cols - 1:
dp[i][j] = combine(dp[i - 1][j], dp[i][j - 1], grid[i][j])
return dp[rows - 1][cols - 1]Unique Paths — dp[i][j] = ways to reach (i, j) moving only right or down
function uniquePaths(rows, cols):
dp = 2D array, rows x cols
for i from 0 to rows - 1:
dp[i][0] = 1 // only one way to reach any cell in column 0: straight down
for j from 0 to cols - 1:
dp[0][j] = 1 // only one way to reach any cell in row 0: straight right
for i from 1 to rows - 1:
for j from 1 to cols - 1:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] // arrived from above, or arrived from the left
return dp[rows - 1][cols - 1]Minimum Path Sum — same shape, min instead of sum
function minPathSum(grid):
rows, cols = grid dimensions
dp = 2D array, rows x cols
dp[0][0] = grid[0][0]
for j from 1 to cols - 1:
dp[0][j] = dp[0][j - 1] + grid[0][j] // row 0: only one way in, from the left
for i from 1 to rows - 1:
dp[i][0] = dp[i - 1][0] + grid[i][0] // column 0: only one way in, from above
for i from 1 to rows - 1:
for j from 1 to cols - 1:
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[rows - 1][cols - 1]Space optimization — collapsing to two rows, or one
function minPathSum(grid):
rows, cols = grid dimensions
prevRow = array of size cols
prevRow[0] = grid[0][0]
for j from 1 to cols - 1:
prevRow[j] = prevRow[j - 1] + grid[0][j]
for i from 1 to rows - 1:
currRow = array of size cols
currRow[0] = prevRow[0] + grid[i][0]
for j from 1 to cols - 1:
currRow[j] = grid[i][j] + min(prevRow[j], currRow[j - 1])
prevRow = currRow
return prevRow[cols - 1]Every cell in the grid is visited exactly one time and does O(1) work per cell. So time is O(rows × cols) for all of these. There is no way around a touch of every cell when every cell's answer genuinely depends on its neighbors. Space for a full table is O(rows × cols). The rolling-row trick above drops that to O(cols), because only the immediately previous row is ever needed again.
| Operation | Time | Space | Why |
|---|---|---|---|
| Unique Paths / Minimum Path Sum — full table | O(rows × cols) | O(rows × cols) | One dp[i][j] is computed per cell, each in O(1) from already-filled neighbors. |
| Unique Paths / Minimum Path Sum — rolling row | O(rows × cols) | O(cols) | The same number of cells is computed, but only the current row and the previous row need to exist in memory at the same time. Everything above that is done being read from. |
Getting the first row/column base case wrong
Row 0 and column 0 do not have both neighbors that the general recurrence expects. Row 0 has no row above it. Column 0 has no column to its left. They follow their own, simpler rule (often "there is exactly one way in" or "carry the running total forward"), and you must apply that rule by hand before the main double loop starts. To reuse the general formula there reads an out-of-bounds cell, or quietly treats a missing neighbor as zero. That is wrong for the count in Unique Paths, and often wrong for the running total in Minimum Path Sum too.
Iterating in the wrong order
dp[i][j] = dp[i-1][j] + dp[i][j-1] assumes that the cell above and the cell to the left are already filled in. This is guaranteed only if the loops go top-to-bottom and left-to-right. If you iterate bottom-to-top or right-to-left by mistake (easy to do if the recurrence is adapted from a different problem without a check of direction), dp[i][j] reads a cell that is still its default or uninitialized value instead of a real answer.
Forgetting an obstacle or blocked-cell case
A grid variant with obstacles (like Unique Paths II) needs an explicit check: if this cell is blocked, dp[i][j] = 0, because no paths reach it, before the general recurrence ever runs. If you skip that check and let the normal dp[i-1][j] + dp[i][j-1] formula apply to a blocked cell, you count paths that walk straight through a wall.
The rolling-row optimization overwriting a value still needed
When you collapse to a single row (not two), dp[j-1] must be the just-updated value for this row, but dp[j] (before you overwrite it) must still be the value of the last row at that same index. If you get the read/write order backward, the in-place update corrupts data that it has not reached yet. The same overwrite risk appears anywhere a DP table is collapsed into fewer rows or variables than states. The direction that you scan changes what is still "old" versus already "new".
Sign in to mark problems done — progress syncs across devices.