Minimum Path Sum

Intuition

The cheapest way to stand on cell (i, j) must have arrived from either the cell above or the cell to the left, whichever costs less, plus the value already sitting in (i, j). That yields dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). The top row and left column are special because they have a single predecessor, so their costs are just running prefix sums. Since each cell only depends on neighbors we have already finalized when scanning row by row, we can write the accumulated cost straight back into the grid and avoid any extra allocation. Processing left to right, top to bottom guarantees both dependencies are ready before we use them. The bottom-right cell ends up holding the minimum total path sum.

Algorithm walkthrough

1. 1Read the dimensions m and n from the grid.
2. 2Iterate rows top to bottom and, within each row, columns left to right.
3. 3Skip the origin (0, 0): its cost is already its own value.
4. 4For the first row (i == 0) only the left neighbor exists, so add grid[i][j-1]; for the first column (j == 0) only the top neighbor exists, so add grid[i-1][j].
5. 5For every interior cell add the smaller of the top and left accumulated costs: grid[i][j] += min(grid[i-1][j], grid[i][j-1]).
6. 6Return grid[m-1][n-1], the minimized total path sum at the destination.

Implementation

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                elif i == 0:
                    grid[i][j] += grid[i][j - 1]
                elif j == 0:
                    grid[i][j] += grid[i - 1][j]
                else:
                    grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
        return grid[m - 1][n - 1]