It's time for Dynamic Programming!

BFS is great for finding the shortest path in an unweighted graph, or Dijkstra for weighted graphs. However, since the movement here is strictly row-by-row, that makes it a Directed Acyclic Graph, which means that using a full graph traversal algorithm is overkill.

We simply need to accumulate results.

Greedy won't work because a small number now might lead us to a massive number later.

Instead, we can use tabulation. We can modify the matrix in place (or create a copy). For every cell, we can ask "If I had to end up at this cell, what is the minimum cost to get here?"

The Recurrence Relation:

To arrive at matrix[row][col], we must have come from one of three places in the row-1:

1. Directly above (row-1, col)
2. Diagonal left: (row-1, col-1)
3. Directly right: (row-1, col+1)

So the value for the current cell becomes:

matrix[r][c] = matrix[r][c] + min(above, left_diag, right_diag).

This will be O(N^2), since we're visiting every cell once. The space is O(1) if we modify the input matrix, and O(N^2) if we make a copy.

At every cell, we're saying: "I don't care about the history of how I got here; I only care about the best score I could possibly have to arrive at this specific spot.

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])

        # Start from the second row (index 1)
        for r in range(1, rows):
            for c in range(cols):
                # 1) Directly above
                best_above = matrix[r-1][c]

                # 2) Diagonal left maybe
                if c > 0:
                    best_above = min(best_above, matrix[r-1][c-1])
                
                # 3) Diagonal right maybe
                if c < cols - 1:
                    best_above = min(best_above, matrix[r-1][c+1])
                
                # Update current cell
                matrix[r][c] += best_above
        return min(matrix[-1])