Minimum Path Sum (LeetCode 64)

The problem

You get an m × n grid of non-negative numbers. Walk from the top-left cell to the bottom-right cell, moving only right or down. The cost of a path is the sum of every cell on it, including both corners. Return the smallest possible cost.

Input:
1 3 1
1 5 1
4 2 1

Output: 7

The path 1 → 3 → 1 → 1 → 1 (right, right, down, down) costs 7.

How to think about it

Start with brute force. Try every right/down path and keep the cheapest. There are C(m+n-2, m-1) paths, which grows exponentially with the grid size, and the same partial paths are re-summed many times.

The key insight: the cheapest way into a cell comes from its cheaper neighbour. You enter (i, j) from above or from the left. Whatever happened before, you want the cheaper of those two arrivals, then you pay this cell’s cost: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). The first row can only be reached from the left and the first column only from above, so those are running sums.

Keep one row. As in Unique Paths, dp[j] before the update holds “above” and dp[j-1] already holds “left”, so one array of length n is enough.

Which pattern is this? 2-D grid DP with a min. The tell is “minimum cost path, moving only right/down”. If moves could go in any direction, this would become a shortest-path problem (Dijkstra) instead.

Approach

1. Copy the first row into dp and turn it into running sums (only reachable from the left).
2. For each later row i: add grid[i][0] to dp[0] (only reachable from above). Then for each j ≥ 1, set dp[j] = grid[i][j] + min(dp[j], dp[j-1]).
3. Return dp[-1].

Solution

def min_path_sum(grid):
    R, C = len(grid), len(grid[0]); dp = grid[0][:]
    for j in range(1, C): dp[j] += dp[j-1]        # first row: only from the left
    for i in range(1, R):
        dp[0] += grid[i][0]                       # first column: only from above
        for j in range(1, C): dp[j] = grid[i][j] + min(dp[j], dp[j-1])   # cheaper of up, left
    return dp[-1]
# min_path_sum([[1,3,1],[1,5,1],[4,2,1]]) -> 7

Dry run

On the example grid, the dp row after each grid row:

For example, in row 1 the middle cell is 5 + min(4, 2) = 7, and the right cell is 1 + min(5, 7) = 6. The answer is dp[-1] = 7.

Complexity

• Time: O(m · n). Each cell is processed once.
• Space: O(n). One row. You could also write the sums into grid itself for O(1) extra space, if modifying the input is allowed.

Edge cases and pitfalls

• Single cell returns its own value; single row or column returns the plain sum.
• Forgetting to copy the first row (dp = grid[0] without [:]) silently modifies the input.
• Greedy (always step to the cheaper neighbour) fails: a cheap step can lead into an expensive region.
• Zeros in the grid are fine; negative values would still work here since there are no cycles.

Related problems

• Unique Paths (LeetCode 62): the same grid shape, counting instead of minimising.
• Dungeon Game (LeetCode 174): a min-cost grid DP that must run backwards from the goal.
• Path With Minimum Effort (LeetCode 1631): moves in all four directions, so it becomes a Dijkstra problem.