<p>Given an <code>n x n</code> array of integers <code>matrix</code>, return <em>the minimum sum of any <strong>falling path</strong> through</em> <code>matrix</code>.</p><p>A <strong>falling path</strong> starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position <code>(row, col)</code> will be <code>(row + 1, col - 1)</code>, <code>(row + 1, col)</code>, or <code>(row + 1, col + 1)</code>.</p>
class Solution: # Time: O(n^2) # Space: O(n) def min_falling_path_sum(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 = dp[col] if col > 0: best = min(best, dp[col - 1]) if col < n - 1: best = min(best, dp[col + 1]) new_dp[col] = matrix[row][col] + best dp = new_dp return min(dp)
