931. Minimum Falling Path Sum

Problem¶

Given an \(n \times n\) integer matrix, find the minimum sum of a path that starts anywhere in the first row and moves to the next row in the same column or one column left or right.

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

minimum path = 1 -> 4 -> 8
output = 13

Key trick¶

Use row-by-row dynamic programming: the minimum path to each cell depends only on the three reachable cells from the previous row.

Trap¶

Updating a single DP array carelessly can overwrite values still needed for neighboring cells; also handle the left and right boundaries correctly.

Why is it interesting?¶

It reduces a two-dimensional path problem to one-dimensional dynamic programming.

Python solution¶

class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        n = len(matrix)
        # dp[c] is the minimum sum of a path ending at column c.
        dp = matrix[0][:]

        for r in range(1, n):
            nxt = [0] * n

            for c in range(n):
                left = dp[c - 1] if c > 0 else float("inf")
                right = dp[c + 1] if c + 1 < n else float("inf")
                nxt[c] = matrix[r][c] + min(left, dp[c], right)

            dp = nxt

        return min(dp)

Time complexity: \(O(n^2)\).

Space complexity: \(O(n)\).

Comment on my solution¶

Your solution is correct and achieves optimal \(O(n^2)\) time and \(O(n)\) auxiliary space.

The in-place update works because prev preserves the old left neighbor, while dp[c] and dp[c + 1] have not yet been overwritten. This is efficient but subtler than using a separate nxt row.

The DP comment should say that dp[c] stores the minimum sum from the current row at column c to the bottom, rather than "from this line at row c."

# Ideas:
# - This is a 1D DP because building the minum path from one cell to another
#   depends only on adjacent rows.
# - must take care to not overwrite DP states of adjacent row before we need it

class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        n = len(matrix)
        # dp[c] min sum of from this line at row c to then bottom
        dp = matrix[-1][:]

        for r in range(n - 2, -1, -1):
            for c in range(n):
                cur = dp[c]
                if c == 0 and c == n - 1:
                    # one column matrix
                    dp[c] += matrix[r][c]
                elif c == 0:
                    dp[c] = matrix[r][c] + min(dp[c], dp[c + 1])
                elif c == n - 1:
                    dp[c] = matrix[r][c] + min(prev, dp[c])
                else:
                    dp[c] = matrix[r][c] + min(prev, dp[c], dp[c + 1])
                prev = cur
        return min(dp)