Minimum Path Sum
Cheapest top-left → bottom-right path in a grid of non-negative costs, moving only right or down.
Open on LeetCode ↗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.
Grid DP where movement is right-and-down only, so every cell depends solely on cells already computed — one sweep in reading order, no recursion. Because each cell is read exactly twice after being written, you can accumulate straight into the input grid and use no extra memory at all.
Approach
State and transition
dp[r][c] = min cost to reach (r,c) = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).
Edges are forced
Top row can only come from the left, first column only from above — running prefix sums, no min needed.
In-place fill
Overwrite the grid itself: no extra memory, and the traversal order (row by row) guarantees dependencies are computed first.
Solution & live demo
Common pitfalls
Handling the first row and column inside the general case
grid[r][c] += min(grid[r-1][c], grid[r][c-1])
if r == 0: grid[r][c] += grid[r][c-1] elif c == 0: grid[r][c] += grid[r-1][c] else: grid[r][c] += min(grid[r-1][c], grid[r][c-1])
On the top row grid[r-1][c] is grid[-1][c], which Python happily reads from the bottom row instead of erroring — you silently mix in values from the far edge of the grid. Edges have only one predecessor and must be treated separately.
Overwriting the starting cell
for r in range(R):
for c in range(C):
grid[r][c] += ...if r == 0 and c == 0: continue
The origin is its own base case — the cost of reaching it is just its value. Adding anything to it double-counts the start and shifts every path total.
Taking the max instead of the min
grid[r][c] += max(grid[r-1][c], grid[r][c-1])
grid[r][c] += min(grid[r-1][c], grid[r][c-1])
The recurrence direction is the whole difference between this problem and its maximise-the-sum sibling. Both compile and run; only one answers the question asked.
Edge cases
Answer is grid[0][0] itself.
Forced path — plain sum, handled by the edge initialization.
Always taking the locally cheaper step can miss a cheap corridor later — that's why DP, not greedy.