# LeetCode 931: Minimum Falling Path Sum

## Problem Restatement

We are given an `n x n` integer matrix.

A falling path starts at any cell in the first row. From a cell `(row, col)`, the next cell must be in the next row and one of these columns:

```text
col - 1
col
col + 1
```

So from `(row, col)`, we may move to:

```text
(row + 1, col - 1)
(row + 1, col)
(row + 1, col + 1)
```

as long as the column stays inside the matrix.

Return the minimum possible sum of a falling path from the first row to the last row. The official statement defines the same down-left, down, and down-right moves.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `n x n` integer matrix |
| Output | Minimum falling path sum |
| Start | Any cell in the first row |
| Move | Down-left, down, or down-right |
| End | Any cell in the last row |

Function shape:

```python
class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        ...
```

## Examples

Example 1:

```python
matrix = [
    [2, 1, 3],
    [6, 5, 4],
    [7, 8, 9],
]
```

One minimum falling path is:

```text
1 -> 5 -> 7
```

The sum is:

```text
1 + 5 + 7 = 13
```

So the answer is:

```python
13
```

Example 2:

```python
matrix = [
    [-19, 57],
    [-40, -5],
]
```

The best path is:

```text
-19 -> -40
```

The sum is:

```text
-59
```

So the answer is:

```python
-59
```

## First Thought: Try Every Path

A direct approach is to start from every cell in the first row and recursively try every valid move.

From each cell, we may have up to three choices in the next row.

This creates many possible paths.

For a matrix with `n` rows, the number of paths can grow exponentially, so plain recursion is too slow.

The repeated work is clear: many different paths can reach the same cell. Once we know the minimum path sum ending at a cell, we should reuse it.

## Key Insight

Use dynamic programming.

Let:

```python
dp[col]
```

mean the minimum falling path sum ending at column `col` in the current row.

For the first row, the best path ending at each column is just the cell value itself.

For every later row, a cell `(row, col)` can be reached only from the previous row at:

```text
col - 1
col
col + 1
```

So the transition is:

```text
new_dp[col] = matrix[row][col] + min(
    dp[col - 1],
    dp[col],
    dp[col + 1]
)
```

We ignore invalid columns outside the matrix.

## Algorithm

Initialize:

```python
dp = matrix[0][:]
```

Then process each row starting from row `1`.

For each column `col`:

1. Start with `best_prev = dp[col]`.
2. If `col > 0`, compare with `dp[col - 1]`.
3. If `col + 1 < n`, compare with `dp[col + 1]`.
4. Set:

```python
new_dp[col] = matrix[row][col] + best_prev
```

After processing the row, replace:

```python
dp = new_dp
```

At the end, return:

```python
min(dp)
```

because the path may end at any column in the last row.

## Walkthrough

Use:

```python
matrix = [
    [2, 1, 3],
    [6, 5, 4],
    [7, 8, 9],
]
```

Initialize from the first row:

```python
dp = [2, 1, 3]
```

Process row `1`:

| Cell | Previous choices | Best previous | New value |
|---|---|---:|---:|
| `6` at col `0` | `2`, `1` | 1 | 7 |
| `5` at col `1` | `2`, `1`, `3` | 1 | 6 |
| `4` at col `2` | `1`, `3` | 1 | 5 |

Now:

```python
dp = [7, 6, 5]
```

Process row `2`:

| Cell | Previous choices | Best previous | New value |
|---|---|---:|---:|
| `7` at col `0` | `7`, `6` | 6 | 13 |
| `8` at col `1` | `7`, `6`, `5` | 5 | 13 |
| `9` at col `2` | `6`, `5` | 5 | 14 |

Now:

```python
dp = [13, 13, 14]
```

Return:

```python
13
```

## Correctness

For the first row, `dp[col] = matrix[0][col]` is correct because a falling path may start at any cell in the first row, and the path sum is exactly that cell value.

Assume before processing row `r`, `dp[col]` stores the minimum falling path sum ending at cell `(r - 1, col)`.

A falling path reaching `(r, col)` must come from one of the valid previous-row cells:

```text
(r - 1, col - 1)
(r - 1, col)
(r - 1, col + 1)
```

By the assumption, `dp` already stores the best possible sum to each of those cells. Therefore, the best path ending at `(r, col)` is the current cell value plus the minimum of those valid previous sums.

The algorithm computes exactly this value for every column in row `r`, so after the row is processed, `new_dp[col]` is correct for that row.

By induction, after the last row, `dp[col]` stores the minimum falling path sum ending at each last-row column.

Since a valid path may end at any column in the last row, the minimum falling path sum overall is `min(dp)`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Every cell is processed once |
| Space | `O(n)` | Only the previous row DP is stored |

## Implementation

```python
class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        n = len(matrix)
        dp = matrix[0][:]

        for row in range(1, n):
            new_dp = [0] * n

            for col in range(n):
                best_prev = dp[col]

                if col > 0:
                    best_prev = min(best_prev, dp[col - 1])

                if col + 1 < n:
                    best_prev = min(best_prev, dp[col + 1])

                new_dp[col] = matrix[row][col] + best_prev

            dp = new_dp

        return min(dp)
```

## Code Explanation

We copy the first row:

```python
dp = matrix[0][:]
```

This avoids modifying the input matrix.

Then we process each later row:

```python
for row in range(1, n):
```

For each cell, the direct above cell is always valid:

```python
best_prev = dp[col]
```

The upper-left cell is valid only when `col > 0`:

```python
if col > 0:
    best_prev = min(best_prev, dp[col - 1])
```

The upper-right cell is valid only when `col + 1 < n`:

```python
if col + 1 < n:
    best_prev = min(best_prev, dp[col + 1])
```

Then we add the current matrix value:

```python
new_dp[col] = matrix[row][col] + best_prev
```

After the row is complete, the new row becomes the previous row for the next iteration:

```python
dp = new_dp
```

The answer is the smallest path sum ending in the last row:

```python
return min(dp)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minFallingPathSum([
        [2, 1, 3],
        [6, 5, 4],
        [7, 8, 9],
    ]) == 13

    assert s.minFallingPathSum([
        [-19, 57],
        [-40, -5],
    ]) == -59

    assert s.minFallingPathSum([
        [5],
    ]) == 5

    assert s.minFallingPathSum([
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]) == 12

    assert s.minFallingPathSum([
        [100, -42, 30],
        [10, -5, 20],
        [7, 8, -9],
    ]) == -56

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[[2,1,3],[6,5,4],[7,8,9]]` | Official-style basic case |
| `[[-19,57],[-40,-5]]` | Negative values |
| `[[5]]` | Single-cell matrix |
| Increasing positive matrix | Checks normal DP movement |
| Mixed signs | Confirms negative path choices |