64. Minimum Path Sum
On LeetCode ->Problem¶
Given a nonempty grid of non-negative integers, find the minimum sum along a path from the top-left to the bottom-right, moving only right or down.
Key trick¶
For each cell, only the cell above and the cell to the left can precede it:
A one-dimensional array can represent the previous and current rows.
Trap¶
- Forgetting to initialize the first row or column correctly.
- Accidentally mutating the input grid.
- Using greedy choices, which do not necessarily produce a globally optimal path.
- Allocating an entire matrix when only the previous row is needed.
Why is it interesting?¶
It is a compact example of turning a path search with overlapping subproblems into dynamic programming, then reducing the space from \(O(mn)\) to \(O(n)\).
Python solution¶
class Solution:
def minPathSum(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = grid[0][:]
# The first row can only be reached by moving right.
for c in range(1, n):
dp[c] += dp[c - 1]
for r in range(1, m):
dp[0] += grid[r][0] # The first column can only be reached by moving down.
for c in range(1, n):
# dp[c] is from above; dp[c - 1] is from the left.
dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
return dp[-1]
Time complexity: \(O(mn)\).
Space complexity: \(O(n)\).
Comment on my solution¶
Your recurrence and boundary initialization are correct, with \(O(mn)\) time and \(O(mn)\) space.
However, dp[0] = grid[0] aliases the input's first row, so
subsequent updates mutate grid. Using dp[0] = grid[0][:] avoids
that side effect. The full matrix can also be reduced to one row, as
in the solution above.
# Ideas:
# - use DP
# - dp[i][j] = minimum path sum for (0,0) to (i,j)
# - dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
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] = grid[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] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
return dp[-1][-1]