LeetCode 64: Minimum Path Sum

Problem Restatement

We are given an m x n grid filled with non-negative integers.

We start at the top-left cell and want to reach the bottom-right cell.

At each step, we may move only:

1. Right
2. Down

A path sum is the sum of all numbers on the path, including the starting cell and the ending cell.

We need to return the minimum possible path sum.

The official constraints are 1 <= m, n <= 200 and 0 <= grid[i][j] <= 200. (leetcode.com)

Input and Output

Function shape:

def minPathSum(grid: list[list[int]]) -> int:
    ...

Examples

For:

grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1],
]

The minimum path is:

1 -> 3 -> 1 -> 1 -> 1

The sum is:

7

So the answer is:

7

For:

grid = [
    [1, 2, 3],
    [4, 5, 6],
]

One minimum path is:

1 -> 2 -> 3 -> 6

The sum is:

12

So the answer is:

12

First Thought: Try Every Path

A direct recursive solution tries every possible path.

From each cell, we try:

1. Move right
2. Move down

Then we take the smaller path sum.

This idea is correct, but it repeats work. Many paths may reach the same cell and recompute the minimum cost from that cell again.

Since the grid may be as large as 200 x 200, repeated recursion is unnecessary.

Key Insight

To reach a cell (row, col), the previous step must come from either:

1. The cell above: (row - 1, col)
2. The cell on the left: (row, col - 1)

So the minimum cost to reach (row, col) is:

grid[row][col] + min(
    cost from above,
    cost from left
)

This gives the dynamic programming transition:

dp[row][col] = grid[row][col] + min(
    dp[row - 1][col],
    dp[row][col - 1],
)

Base Cases

The starting cell has only one path:

dp[0][0] = grid[0][0]

The first row can only be reached from the left:

dp[0][col] = dp[0][col - 1] + grid[0][col]

The first column can only be reached from above:

dp[row][0] = dp[row - 1][0] + grid[row][0]

Algorithm

Create a DP table with the same size as the grid.

Set the top-left value.

Fill the first row.

Fill the first column.

Then fill every remaining cell using:

dp[row][col] = grid[row][col] + min(
    dp[row - 1][col],
    dp[row][col - 1],
)

Return:

dp[m - 1][n - 1]

Correctness

The robot may move only right or down. Therefore every path to cell (row, col) must arrive from either the cell above or the cell on the left.

For the first row, the robot can only move right, so each cell has exactly one possible path from the start. For the first column, the robot can only move down, so each cell also has exactly one possible path.

For every other cell, the best path must use the cheaper of the best path to the cell above and the best path to the cell on the left, then add the current cell value.

The algorithm computes cells in row-major order, so when it computes dp[row][col], both needed previous values are already known. Thus every DP value is correct, and the bottom-right value is the minimum path sum.

Complexity

Implementation

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        dp = [[0] * n for _ in range(m)]

        dp[0][0] = grid[0][0]

        for col in range(1, n):
            dp[0][col] = dp[0][col - 1] + grid[0][col]

        for row in range(1, m):
            dp[row][0] = dp[row - 1][0] + grid[row][0]

        for row in range(1, m):
            for col in range(1, n):
                dp[row][col] = grid[row][col] + min(
                    dp[row - 1][col],
                    dp[row][col - 1],
                )

        return dp[m - 1][n - 1]

Code Explanation

First get the grid size:

m = len(grid)
n = len(grid[0])

Create a DP table:

dp = [[0] * n for _ in range(m)]

Initialize the starting cell:

dp[0][0] = grid[0][0]

Fill the first row:

for col in range(1, n):
    dp[0][col] = dp[0][col - 1] + grid[0][col]

Fill the first column:

for row in range(1, m):
    dp[row][0] = dp[row - 1][0] + grid[row][0]

For each inner cell, choose the cheaper previous route:

dp[row][col] = grid[row][col] + min(
    dp[row - 1][col],
    dp[row][col - 1],
)

Finally return the bottom-right cell:

return dp[m - 1][n - 1]

Space Optimization

Each cell only depends on:

1. The value above it
2. The value to its left

So we can keep one row.

Let dp[col] mean the minimum path sum to the current row at column col.

When processing a cell:

dp[col] = grid[row][col] + min(dp[col], dp[col - 1])

Here:

Optimized Implementation

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        dp = [0] * n
        dp[0] = grid[0][0]

        for col in range(1, n):
            dp[col] = dp[col - 1] + grid[0][col]

        for row in range(1, m):
            dp[0] += grid[row][0]

            for col in range(1, n):
                dp[col] = grid[row][col] + min(
                    dp[col],
                    dp[col - 1],
                )

        return dp[-1]

Testing

def run_tests():
    s = Solution()

    assert s.minPathSum([
        [1, 3, 1],
        [1, 5, 1],
        [4, 2, 1],
    ]) == 7

    assert s.minPathSum([
        [1, 2, 3],
        [4, 5, 6],
    ]) == 12

    assert s.minPathSum([[5]]) == 5

    assert s.minPathSum([[1, 2, 3]]) == 6

    assert s.minPathSum([
        [1],
        [2],
        [3],
    ]) == 6

    assert s.minPathSum([
        [0, 0],
        [0, 0],
    ]) == 0

    print("all tests passed")

run_tests()