Minimum Path Sum Solution

Problem

Given an m×n grid of non-negative integers, find a path from the top-left corner to the bottom-right corner that minimizes the total sum of all values along the path. You may only move right or down at each step.

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The path 1 → 3 → 1 → 1 → 1 (right, right, down, down) gives the minimum sum of 7.

A tempting but suboptimal path would be 1 → 1 → 5 → 1 → 1 = 9 (down, right, right, down) — greedily taking the smallest immediate neighbor doesn't always win, which is why greedy fails and DP is needed.

Intuition

At any cell (i, j), the only two ways to arrive are from directly above (i−1, j) or from the left (i, j−1). The cheapest route to (i, j) is therefore the grid value at that cell plus whichever of those two predecessors had the smaller accumulated cost. Building this up from top-left to bottom-right fills the entire table with optimal subproblem answers, and the bottom-right cell holds the final answer.

Approach 1 — 2D Dynamic Programming

Construct a separate dp table where dp[i][j] stores the minimum path cost to reach cell (i, j). Seed the first row and first column (each has only one direction to arrive from), then fill the rest with the recurrence.

Allocate a dp table of the same size as the grid.
Set dp[0][0] = grid[0][0] — the starting cell has no predecessor.
Fill the first row left-to-right: dp[0][col] = dp[0][col−1] + grid[0][col] (only source is left).
Fill the first column top-to-bottom: dp[row][0] = dp[row−1][0] + grid[row][0] (only source is above).
For every remaining cell: dp[row][col] = grid[row][col] + min(dp[row−1][col], dp[row][col−1]).
Return dp[rows−1][cols−1].

1def minPathSum(self, grid: list[list[int]]) -> int:
2    rows, cols = len(grid), len(grid[0])
3    dp = [[0] * cols for _ in range(rows)]
4
5    dp[0][0] = grid[0][0]
6
7    for col in range(1, cols):
8        dp[0][col] = dp[0][col - 1] + grid[0][col]  # first row: only reachable from the left
9
10    for row in range(1, rows):
11        dp[row][0] = dp[row - 1][0] + grid[row][0]  # first column: only reachable from above
12
13    for row in range(1, rows):
14        for col in range(1, cols):
15            dp[row][col] = grid[row][col] + min(dp[row - 1][col], dp[row][col - 1])
16
17    return dp[rows - 1][cols - 1]

Time: O(m × n) — every cell is computed exactly once.
Space: O(m × n) — the full dp table is kept in memory.

Approach 2 — Space-Optimized DP (1D Array)

A single 1D array of length cols can replace the 2D table. Before we update dp[col] for the current row, it still holds the minimum cost to reach the previous row's same column — that is the "from above" value. After updating dp[col−1] this row, it holds the "from left" value. So the same two-predecessor recurrence works in-place.

Initialize dp from the first row of the grid (cumulative left-to-right sums).
For each subsequent row, update dp[0] by adding grid[row][0] (only path is down the first column).
For columns 1 through cols−1: dp[col] = grid[row][col] + min(dp[col], dp[col−1]), where dp[col] is still the above-row value and dp[col−1] is the already-updated left value.
Return dp[cols−1] after all rows are processed.

1def minPathSum(self, grid: list[list[int]]) -> int:
2    rows, cols = len(grid), len(grid[0])
3
4    dp = [0] * cols
5    dp[0] = grid[0][0]
6    for col in range(1, cols):
7        dp[col] = dp[col - 1] + grid[0][col]  # seed with first-row cumulative sums
8
9    for row in range(1, rows):
10        dp[0] += grid[row][0]  # first column: accumulate downward, no left neighbor
11        for col in range(1, cols):
12            # dp[col] still holds the minimum from the previous row (from above)
13            # dp[col - 1] was just updated this row (from the left)
14            dp[col] = grid[row][col] + min(dp[col], dp[col - 1])
15
16    return dp[cols - 1]

Time: O(m × n) — same recurrence, same number of cells visited.
Space: O(n) — only a single row of dp values is kept alive at any time.

Complexity Summary

Approach	Time	Space	When to use
2D DP	O(m × n)	O(m × n)	When you need to reconstruct the actual path afterward
1D DP (Space-Optimized)	O(m × n)	O(n)	Default; saves memory when only the minimum cost is needed

Common Mistakes

Initializing dp[0][0] to 0 instead of grid[0][0] — the top-left cell is part of the path and its cost must be counted; starting at 0 under-counts every path's total.
Skipping the first-row and first-column base cases — cells on the edges have only one source direction; applying min(above, left) to them would silently read an uninitialized 0 as an unrealistically cheap predecessor.
Forgetting that dp[col] in the 1D approach still holds the previous row's value — this dual role is the trick that makes in-place updates work; overwriting dp[col] before reading it destroys the "from above" information.
Confusing m (rows) and n (cols) in the loop bounds — swapping them causes the iteration to go out of bounds or skip cells entirely; always derive rows = grid.length and cols = grid[0].length explicitly.
Thinking greedy works — always choosing the smaller immediate neighbor can miss a locally expensive cell that leads to a globally cheaper path; DP is required because the grid has overlapping subproblems.

Minimum Path Sum — Solution