Minimum Path Sum LeetCode 64 — Grid DP

LeetCode 64 Minimum Path Sum gives you an m × n grid filled with non-negative integers. Starting from the top-left cell (0, 0), you must reach the bottom-right cell (m-1, n-1) by moving only right or down at each step. The goal is to find the path that minimizes the sum of all numbers along the path, including the start and end cells.

This is one of the most instructive 2D DP problems because it has a clean recurrence, a natural base case, and multiple space optimization levels. It also directly connects to Unique Paths (LeetCode 62), which counts paths through the same grid structure. Once you internalize the DP table setup here, problems like Dungeon Game and the Triangle problem become much easier to approach.

Constraints: 1 ≤ m, n ≤ 200, 0 ≤ grid[i][j] ≤ 100. All values are non-negative, which means a greedy approach of always choosing the locally smallest neighbor is tempting — but it fails to find the global minimum in general grids.

A greedy approach would always move to the neighbor (right or down) with the smaller value at each step. This is intuitive but incorrect. Consider a grid where moving right first leads to a costly cell that blocks access to cheaper cells later, while moving down initially costs more but opens up a much cheaper corridor to the destination.

The reason greedy fails here is that each decision affects all future options. You cannot evaluate a move in isolation — the cost of a path depends on the entire sequence of choices from start to finish. To find the true minimum, you must consider all valid paths. That exponential search is what DP collapses into a polynomial-time computation by storing and reusing subproblem results.

Specifically, a greedy solution can be fooled by grids like [[1,3,1],[1,5,1],[4,2,1]] where the greedy path (right, right, down, down) gives 1+3+1+1+1=7 but the optimal path (down, right, right, down) gives 1+1+3+1+1=7 — and other grids where greedy is strictly worse than optimal. DP guarantees correctness by building up the answer from all subproblems simultaneously.

Define dp[i][j] as the minimum sum path cost to reach cell (i, j) from (0, 0). The recurrence is: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). At each cell, the cheapest way to arrive is either from above (dp[i-1][j]) or from the left (dp[i][j-1]) — whichever is smaller. We add the current cell's value on top.

The base cases handle the first row and first column separately. For the first row (i=0), you can only arrive from the left: dp[0][j] = dp[0][j-1] + grid[0][j]. For the first column (j=0), you can only arrive from above: dp[i][0] = dp[i-1][0] + grid[i][0]. The starting cell dp[0][0] = grid[0][0]. After initialization, fill dp in row-major order.

After filling the entire dp table, the answer is dp[m-1][n-1]. This approach uses O(m×n) time (each cell computed once) and O(m×n) space for the dp table. The 2D table version is the clearest to understand and verify correctness before optimizing space.

The first space optimization is to eliminate the separate dp table by modifying the input grid in-place. Since dp[i][j] depends only on grid[i][j] (the original value) plus the already-computed dp values of the cells above and to the left, you can safely overwrite grid[i][j] with the cumulative minimum cost. The original value has already been used in the recurrence before it gets overwritten.

The in-place approach reduces space from O(m×n) to O(1) extra space (beyond the input). The first row becomes prefix sums: grid[0][j] += grid[0][j-1]. The first column becomes prefix sums: grid[i][0] += grid[i-1][0]. Then for interior cells: grid[i][j] += min(grid[i-1][j], grid[i][j-1]). The recurrence is identical — only the storage location changes from a new array to the grid itself.

The trade-off is that you permanently modify the caller's input. In many real systems, mutating input is undesirable. Some interviewers will ask you to note this side effect and whether the problem permits it. If input must be preserved, use the 1D rolling array approach instead.

The recurrence dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) only accesses the current row and the previous row. This means you do not need to store the entire m×n dp table — a single 1D array of length n suffices. At any point during computation, dp[j] holds the minimum cost to reach the current row at column j, and dp[j] (before update) holds the cost from the previous row at column j.

Process one row at a time. Initialize the 1D array dp with the prefix sums of the first row. Then for each subsequent row i, update dp[0] += grid[i][0] (first column only has one source: above). For j from 1 to n-1, dp[j] = grid[i][j] + min(dp[j], dp[j-1]). Here dp[j] (not yet updated in this iteration) is the value from the row above, and dp[j-1] (already updated) is the value from the left in the current row.

This 1D approach uses O(n) extra space regardless of m. It is the most space-efficient solution without in-place mutation. For a 200×200 grid the saving is modest in practice, but the technique is essential to know because it generalizes to all 2D grid DP problems where each row only depends on the previous row.

Python (2D DP): m, n = len(grid), len(grid[0]); dp = [[0]*n for _ in range(m)]; dp[0][0] = grid[0][0]; fill first row and column with prefix sums; then for i in range(1,m): for j in range(1,n): dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]); return dp[m-1][n-1]. Time O(m×n), space O(m×n). Python (1D): dp = list(itertools.accumulate(grid[0])); then for each row update dp in place. Return dp[-1]. Space O(n).

Java (in-place): for (int j=1; j<n; j++) grid[0][j]+=grid[0][j-1]; for (int i=1; i<m; i++) grid[i][0]+=grid[i-1][0]; for (int i=1; i<m; i++) for (int j=1; j<n; j++) grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]); return grid[m-1][n-1]. Space O(1). Java (1D): int[] dp = Arrays.copyOf(grid[0],n); for (int j=1;j<n;j++) dp[j]+=dp[j-1]; then for each row, dp[0]+=grid[i][0], then dp[j]=grid[i][j]+Math.min(dp[j],dp[j-1]). Return dp[n-1].

All three variants — 2D DP, in-place, and 1D rolling — have identical O(m×n) time complexity. The difference is only in space: O(m×n) for 2D, O(1) extra for in-place, and O(n) extra for 1D. In an interview, presenting the 2D solution first and then explaining the optimizations demonstrates strong command of the problem.

Minimum Path Sum belongs to a cluster of grid DP problems that all share the same constraint: moves are restricted to right and down only. Unique Paths (LeetCode 62) counts the total number of such paths — the recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1] (addition instead of min). Unique Paths II (LeetCode 63) adds obstacles, requiring a check before applying the recurrence.

Triangle (LeetCode 120) is a variant where the grid is triangular and you move from the apex to the base. The bottom-up DP processes from the last row upward, making it slightly different in iteration direction but conceptually identical. Dungeon Game (LeetCode 174) adds a constraint that HP must stay positive — which forces a reverse DP from bottom-right to top-left because the constraint is on the future, not the past.

Mastering Minimum Path Sum gives you the template for all these problems. The key skills are: (1) identifying the correct recurrence from move constraints, (2) handling boundary rows/columns carefully, (3) reducing 2D DP to 1D by noting which rows are actually needed. These three skills transfer directly to Triangle, Unique Paths II, and even more advanced grid problems like Cherry Pickup (LeetCode 741).