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've already solved" idea spread across two axes instead of one — dp[i][j] depends on neighboring cells in a grid, not just the one or two entries before it in a line. Nothing conceptually new happens here; the table just grew a second dimension.
Picture filling in a grid of answers cell by cell — "how many ways to get here" or "what's the cheapest path to here" — where each cell only needs 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, left to right within each row, and by the time you reach any cell, everything it depends on is already sitting there waiting.
A 2D table, filled in reading order
function solve(grid):
rows, cols = grid dimensions
dp = 2D array, rows x cols
# base case row/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 once and does O(1) work per cell, so time is O(rows × cols) across the board — no way around touching 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), since 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] computed per cell, each in O(1) from already-filled neighbors. |
| Unique Paths / Minimum Path Sum — rolling row | O(rows × cols) | O(cols) | Same number of cells computed, but only the current and previous row need to exist in memory at once — everything above that is done being read from. |
Getting the first row/column base case wrong
Row 0 and column 0 don't have both neighbors 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 just "there's exactly one way in" or "carry the running total forward"), and that rule has to be applied by hand before the main double loop starts. Reusing the general formula there reads an out-of-bounds cell or silently treats a missing neighbor as zero, which is wrong for Unique Paths' count and often wrong for Minimum Path Sum's running total too.
Iterating in the wrong order
dp[i][j] = dp[i-1][j] + dp[i][j-1] assumes the cell above and the cell to the left are already filled in — which is only guaranteed if the loops go top-to-bottom, left-to-right. Iterate bottom-to-top or right-to-left by mistake (easy to do if the recurrence gets adapted from a different problem without checking direction) and dp[i][j] reads a cell that's still its default/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 — no paths reach it, full stop — before the general recurrence ever runs. Skipping that check and letting the normal dp[i-1][j] + dp[i][j-1] formula apply to a blocked cell counts paths that walk straight through a wall.
The rolling-row optimization overwriting a value still needed
When collapsing 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) still needs to be last row's value at that same index — get the read/write order backwards and the in-place update corrupts data it hasn't gotten to yet. The same overwrite risk shows up anywhere a DP table is collapsed into fewer rows/variables than states: which direction you scan changes what's still "old" versus already "new."
Sign in to mark problems done — progress syncs across devices.