Third in the grid-DP trio, and the one where the problem stops counting and starts optimising. The table looks identical to Unique Paths and the loop is the same shape, but one operator changes and with it the entire class of problem — and that change is exactly what makes the greedy answer wrong.
The problem
Given an m × n grid of non-negative numbers, find a path from top-left to
bottom-right that minimises the sum of the numbers along it. You may only move right or down.
[[1,3,1], -> 7 1 -> 3 -> 1 -> 1 -> 1
[1,5,1],
[4,2,1]]
[[1,2,3], -> 12 1 -> 2 -> 3 -> 6
[4,5,6]]
[[5]] -> 5 the start counts tooWhy greedy fails
The tempting answer is "at each step take the smaller of right and down". It is wrong, and it is worth constructing the counterexample rather than just asserting it — an interviewer who hears "the greedy does not work" wants to know whether you can show it.
[[1, 2, 100],
[1, 100, 100],
[1, 1, 1]]
greedy from (0,0): right to 2 looks cheaper than down to 1
...and then every continuation is expensive.
best path: straight down the 1s, then right: 1+1+1+1+1 = 5The cheap move now commits you to expensive moves later, and a greedy has no way to see that. This is the standard reason a problem is DP and not greedy: local optimality does not compose into global optimality. Being able to say that sentence and back it with a grid is the answer.
The recurrence
Same question as before — how did I get here? — with min where the counting version
had +, and the cell's own cost added on:
cost[r][c] = grid[r][c] + min(cost[r-1][c], cost[r][c-1])
cost[0][0] = grid[0][0]
top row = running sum rightwards (no cell above)
left column= running sum downwards (no cell to the left)The edges are not a special rule so much as the general rule with one neighbour missing. A missing neighbour is not zero here — zero would be a free path in from outside the grid, which would make every edge cell think it could be reached cheaply. It is infinity, which is why the implementations below either handle the edges explicitly or seed with a large sentinel.
That sign flip is the single most common bug when someone adapts the Unique Paths code: in a counting problem the missing neighbour contributes 0, in a minimising problem it contributes ∞.
Java
class Solution {
public int minPathSum(int[][] grid) {
int n = grid[0].length;
int[] row = new int[n];
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) {
row[c] = grid[r][c]; // the start
} else if (r == 0) {
row[c] = row[c - 1] + grid[r][c]; // top row: only from the left
} else if (c == 0) {
row[c] = row[c] + grid[r][c]; // left column: only from above
} else {
row[c] = Math.min(row[c], row[c - 1]) + grid[r][c];
}
}
}
return row[n - 1];
}
}row[c] on the right-hand side is still the cell above — the previous row's value,
not yet overwritten — while row[c - 1] is the current row. Reading before writing is
what makes one array enough, exactly as in Unique Paths.
Four branches reads like a lot for a DP this small. The alternative is seeding the row with
Integer.MAX_VALUE and a single uniform line, and it is tempting — but
MAX_VALUE + grid[r][c] overflows to a negative number and the min then
happily picks the path through the wall. Use a sentinel like Integer.MAX_VALUE / 2 if
you want the uniform version, and say why.
Python
class Solution:
def minPathSum(self, grid: list[list[int]]) -> int:
n = len(grid[0])
row = [float("inf")] * n
for r, grid_row in enumerate(grid):
for c in range(n):
if r == 0 and c == 0:
row[c] = grid_row[c]
elif c == 0:
row[c] = row[c] + grid_row[c] # only from above
elif r == 0:
row[c] = row[c - 1] + grid_row[c] # only from the left
else:
row[c] = min(row[c], row[c - 1]) + grid_row[c]
return int(row[-1])Python's float("inf") genuinely cannot overflow, which makes the sentinel approach
safe here in a way it is not in Java. The int() on the way out matters: without it a
grid that never touched the sentinel still returns an int, but the type checker sees a
float, and returning 7.0 where 7 was asked for is the kind of
thing that fails a strict comparison somewhere downstream.
Complexity
| Time | Space | |
|---|---|---|
| Rolling row | O(m · n) | O(n) |
| In place | O(m · n) | O(1), destroys the input |
Every cell is read once and there is no way to do better — the answer can depend on any cell, so any correct algorithm must look at all of them.
Two follow-ups worth having ready
"Return the path, not just the sum." Keep the full table rather than one row,
then walk backwards from the bottom-right, at each step moving to whichever of the two predecessors
the recurrence actually chose. That costs the O(m · n) space back, which is the honest
trade: the rolling row throws away precisely the information a path reconstruction needs.
"What if negative numbers were allowed?" The DP still works, because right-and-down movement means no cell can be revisited and there are no cycles to exploit. If diagonal or upward moves were added, a negative cycle would make "minimum" undefined and the problem becomes shortest path — Dijkstra if weights stay non-negative, Bellman-Ford otherwise. Knowing where the DP stops being valid is more interesting than the DP.
The pattern
Unique Paths (62) is this with
+ instead of min;
Unique Paths II (63) adds the
obstacle guard. Triangle (120) is the same recurrence on a triangular grid. Dungeon Game (174) looks
identical and is not — it has to be computed backwards from the destination, because the constraint
is on the running minimum rather than the total, and that is a genuinely instructive failure to
attempt forwards.
What the interviewer is checking
- That you can construct a grid where the greedy loses, not just claim it does.
minin place of+, and the cell's own value added on.- That a missing neighbour is ∞ here, where it was 0 in the counting version.
- The top row and left column, and that
grid[0][0]is included in the sum. - The
MAX_VALUEoverflow if you go the sentinel route. - The single-cell grid.
- That you can say what would break with upward moves allowed.