LeetCode #64 Medium

Minimum Path Sum

Cheapest top-left → bottom-right path in a grid of non-negative costs, moving only right or down.

dpgrid

02

Intuition

💡

You can only arrive at a cell from above or from the left, so the cheapest way to reach it is its own cost plus the cheaper of those two arrivals. Fill the grid in reading order and every cell's answer is ready when you need it — the bottom-right cell ends up holding the global minimum.

03

Approach

1

State and transition

dp[r][c] = min cost to reach (r,c) = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).

2

Edges are forced

Top row can only come from the left, first column only from above — running prefix sums, no min needed.

3

In-place fill

Overwrite the grid itself: no extra memory, and the traversal order (row by row) guarantees dependencies are computed first.

04

Solution & live demo

python

▶1class Solution:
▶2    def minPathSum(self, grid):
▶3        R, C = len(grid), len(grid[0])
▶4        for r in range(R):
▶5            for c in range(C):
▶6                if r == 0 and c == 0: continue
▶7                if r == 0:   grid[r][c] += grid[r][c-1]
▶8                elif c == 0: grid[r][c] += grid[r-1][c]
▶9                else:        grid[r][c] += min(grid[r-1][c], grid[r][c-1])
▶10        return grid[-1][-1]

05

Edge cases

Single cell

Answer is grid[0][0] itself.

Single row or column

Forced path — plain sum, handled by the edge initialization.

Greedy fails

Always taking the locally cheaper step can miss a cheap corridor later — that's why DP, not greedy.

06

Complexity

Time

O(R·C)

Space

O(1)

Grid reused as the DP table.