Minimum Path Sum
Minimum Path Sum: cheapest top-left → bottom-right path in a grid of non-negative costs, moving only right or down.
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
Intuition
Minimum path sum asks for the cheapest route from the top-left of a grid to the bottom-right, moving only right or down. The number of such paths grows combinatorially, so enumerating them is hopeless — but the movement restriction makes dynamic programming immediate.
Because you can only move right or down, there are exactly two ways to arrive at any cell: from the cell above, or from the cell to the left. The cheapest way to reach a cell is therefore its own cost plus the cheaper of those two arrivals:
- dp[r][c] = grid[r][c] + min(dp[r−1][c], dp[r][c−1])
Nothing else can influence it, because no path can approach from the right or from below.
The edges are simpler still. The top row has no cell above it, so each entry is just a running total from the left; the first column likewise accumulates downward. Those are not special cases so much as the general rule with one option missing.
Filling in reading order — left to right, top to bottom — guarantees both dependencies are already computed when each cell is reached. That ordering is what makes the bottom-up version correct without recursion or memoisation bookkeeping.
Since each cell is read exactly twice and then never again, the grid can be overwritten in place for O(1) extra space, or a single row kept for O(n).
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
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(R·C) time and O(1) space.
Identify the two possible arrivals
Moving only right or down means a cell is reachable solely from above or from the left. That restriction is what makes the recurrence exact — with diagonal or upward moves allowed, the dependency graph would have cycles and this approach would fail.
Write the recurrence
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]). The cell's own cost is always paid; the only choice is which neighbour to arrive from, and taking the cheaper one is optimal because the remaining journey is independent of how you got here.
Handle the first row and column
The top row can only be entered from the left and the first column only from above, so each is a running prefix sum with no minimum to take. Filling them first means the main loop never needs a bounds check.
Fill in reading order
Process rows top to bottom and columns left to right. This order guarantees dp[r-1][c] and dp[r][c-1] are already final when dp[r][c] is computed, which is exactly why no recursion is needed.
Overwrite the grid to save space
Each cell's original value is used once and never again, so the result can be written straight into the input for O(1) extra space. If mutating the input is disallowed, a single row of size cols suffices, updated left to right.
Cost of the fill
Every cell is computed once with O(1) work, giving O(rows × cols) time. Space is O(1) in place, or O(cols) with a rolling row — compare with enumerating paths, which is exponential.
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.