# 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](https://leetcode.com/problems/minimum-path-sum/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 2D grid of non-negative integers |
| Output | The minimum path sum from top-left to bottom-right |
| Start | `(0, 0)` |
| Target | `(m - 1, n - 1)` |
| Allowed moves | Right or down |

Function shape:

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

## Examples

For:

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

The minimum path is:

```text
1 -> 3 -> 1 -> 1 -> 1
```

The sum is:

```python
7
```

So the answer is:

```python
7
```

For:

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

One minimum path is:

```text
1 -> 2 -> 3 -> 6
```

The sum is:

```python
12
```

So the answer is:

```python
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:

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

This gives the dynamic programming transition:

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

## Base Cases

The starting cell has only one path:

```python
dp[0][0] = grid[0][0]
```

The first row can only be reached from the left:

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

The first column can only be reached from above:

```python
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:

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

Return:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | Every cell is processed once |
| Space | `O(m * n)` | The DP table stores one value per cell |

## Implementation

```python
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:

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

Create a DP table:

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

Initialize the starting cell:

```python
dp[0][0] = grid[0][0]
```

Fill the first row:

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

Fill the first column:

```python
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:

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

Finally return the bottom-right cell:

```python
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:

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

Here:

| Expression | Meaning |
|---|---|
| `dp[col]` before update | Cost from above |
| `dp[col - 1]` | Cost from left |

## Optimized Implementation

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `3 x 3` grid | Standard example |
| `2 x 3` grid | Rectangular example |
| Single cell | Start equals target |
| Single row | Only right moves |
| Single column | Only down moves |
| All zeros | Minimum sum can be zero |