Minimum Falling Path Sum

Intuition

The minimum sum to reach a cell only depends on the three cells immediately above it: the one directly above and its two diagonal neighbors. That gives an optimal-substructure recurrence where each cell stores the smallest path total that ends there. We build these totals from the first row downward, so by the time we process row i we already know every optimal answer for row i - 1. Since a cell only reads the previous row, we can keep just one rolling array of size n. The final answer is the minimum value across the last row, because a path may end at any column.

Algorithm walkthrough

1. 1Initialize the rolling array dp to a copy of the first row; dp[j] is the best path sum ending at column j.
2. 2For each subsequent row i, snapshot the previous row's totals as prev before overwriting.
3. 3For each column j, take best = min(prev[j], prev[j-1], prev[j+1]) while skipping neighbors that fall outside the grid.
4. 4Set dp[j] = matrix[i][j] + best, folding the current cell's value into the cheapest arrival.
5. 5After the last row is processed, return the minimum entry of dp as the overall answer.

Implementation

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        dp = matrix[0][:]
        for i in range(1, n):
            prev = dp[:]
            for j in range(n):
                best = prev[j]
                if j > 0:
                    best = min(best, prev[j - 1])
                if j < n - 1:
                    best = min(best, prev[j + 1])
                dp[j] = matrix[i][j] + best
        return min(dp)