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: from the top-left, at each cell branch into “go right” and “go down,” and take the cheaper full path. Symmetrically (and easier to memoize), work backward: the cost to reach (i, j) is its value plus the cheaper of reaching the cell above or the cell to its left.
class Solution:
def minPathSum(self, 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 the constraints kill it: 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
The insight: dfs(i, j) depends only on (i, j), and there are just m × n cells. Cache them.
from functools import lru_cache
class Solution:
def minPathSum(self, 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])
class Solution:
def minPathSum(self, 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
The insight: 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.
class Solution:
def minPathSum(self, 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.