931. Minimum Falling Path Sum

931. Minimum Falling Path Sum

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        @cache
        def dp(row, col):
            if row >= rows:
                return 0
            if col < 0 or col >= cols:
                return float('inf')
            
            return matrix[row][col] + min(dp(row + 1, col - 1), dp(row + 1, col), dp(row + 1, col + 1))
            
        
        res = float('inf')
        for i in range(cols):
            res = min(res, dp(0, i))
        
        return res