TL;DR
Grid DP: dp[i][j] = cheapest cost to reach (i, j) — O(m × n) time, O(n) space after rolling to one row.
Approach 1 — Brute-force recursion
Intuition: the cost to reach (i, j) is its own value plus the cheaper of reaching the cell above or the cell to its left. Recursing on those two predecessors reaches the base case at (0, 0). Working backward like this (rather than branching forward into “right” and “down”) is easier to memoize, since each call is keyed by a single cell.
def minPathSum(grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
def dfs(i: int, j: int) -> int:
if i == 0 and j == 0:
return grid[0][0]
if i < 0 or j < 0:
return float("inf")
return grid[i][j] + min(dfs(i - 1, j), dfs(i, j - 1))
return dfs(m - 1, n - 1)
Complexity: O(2^(m+n)) time (two-way branch per cell), O(m+n) recursion depth.
Why it fails at scale: at 200×200 the number of distinct top-left-to-bottom-right paths is C(400, 200), a number with over a hundred digits.
Approach 2 — Top-down memoization
dfs(i, j) depends only on (i, j), and there are just m × n cells, so caching each result collapses the exponential blowup.
from functools import lru_cache
def minPathSum(grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
@lru_cache(maxsize=None)
def dfs(i: int, j: int) -> int:
if i == 0 and j == 0:
return grid[0][0]
if i < 0 or j < 0:
return float("inf")
return grid[i][j] + min(dfs(i - 1, j), dfs(i, j - 1))
return dfs(m - 1, n - 1)
Complexity: O(m × n) time and space.
Approach 3 — Bottom-up 2-D table
Table meaning: dp[i][j] = minimum sum of any right/down path from (0, 0) to (i, j).
2-D recurrence:
dp[0][0] = grid[0][0]
dp[0][j] = dp[0][j-1] + grid[0][j] # first row: only "from left"
dp[i][0] = dp[i-1][0] + grid[i][0] # first col: only "from above"
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
Each interior cell reads its two already-computed neighbors:
flowchart LR
Above["dp[i-1][j]<br/>above"] --> Cell["dp[i][j] = grid[i][j] + min(above, left)"]
Left["dp[i][j-1]<br/>left"] --> Cell
Filling top-to-bottom, left-to-right guarantees both neighbors are ready before a cell is computed.
def minPathSum(grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n):
dp[0][j] = dp[0][j - 1] + grid[0][j]
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[m - 1][n - 1]
Walkthrough on [[1, 3, 1], [1, 5, 1], [4, 2, 1]]:
| dp | col0 | col1 | col2 |
|---|
| row0 | 1 | 4 | 5 |
| row1 | 2 | 7 | 6 |
| row2 | 6 | 8 | 7 |
dp[1][2] = 1 + min(5, 7) = 6, and dp[2][2] = 1 + min(6, 8) = 7. Answer 7, matching the right, right, down, down path.
Complexity: O(m × n) time, O(m × n) space.
Approach 4 — Space-optimized rolling row
dp[i][j] reads only the cell above (previous row, same column) and the cell to the left (current row, already updated). A single row of length n, updated left to right, carries both: before overwriting dp[j] it still holds the value from the row above, and dp[j-1] already holds the current row’s left neighbor.
def minPathSum(grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = grid[0][0]
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j] # first row
for i in range(1, m):
dp[0] += grid[i][0] # first column
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j - 1]) # dp[j]=above, dp[j-1]=left
# end row
return dp[n - 1]
Complexity: O(m × n) time, O(n) space.
Common pitfalls
- Forgetting the first row/column are prefix sums — those cells have only one predecessor; initializing them to
grid values (not cumulative sums) understates the cost.
- Allowing diagonal or upward moves — only right and down are legal; the recurrence must read exactly the two neighbors above and to the left.
- Mutating
grid in place — a valid space-saving trick, but only if the caller tolerates a modified input; the rolling-row version avoids that risk.
- In the rolled version, remember
dp[0] += grid[i][0] handles the first column before the inner loop, since column 0 has no left neighbor.
Pattern takeaway
Grid path DP is the most direct 2-D DP: each cell’s optimum is its own weight plus the best reachable predecessor, and the legal moves determine which neighbors you read. Fill in the order the dependencies require (here top-to-bottom, left-to-right), and since each cell needs only the previous row and the current left neighbor, one rolling row gives O(n) space.