931-Minimum-Falling-Path-Sum.py

class Solution:    
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:        
        Memo = {}        
        def Path(i, k, n):            
            if (i, k) in Memo:                
                return Memo[(i, k)]            
            if i == n - 1:                
                return matrix[i][k]            
            if k > 0 and k < n - 1:                
                Psx = matrix[i][k] + Path(i + 1, k - 1, n)                
                Pst = matrix[i][k] + Path(i + 1, k, n)                
                Pdx = matrix[i][k] + Path(i + 1, k + 1, n)                
                Memo[(i, k)] = min(min(Pdx, Pst), Psx)                
                return Memo[(i, k)]            
            else:                
                if k == 0:                
                    Pst = matrix[i][k] + Path(i + 1, k, n)                
                    Pdx = matrix[i][k] + Path(i + 1, k + 1, n)                    
                    Memo[(i, k)] = min(Pst, Pdx)                    
                    return Memo[(i, k)]                    
                else:                  
                    Psx = matrix[i][k] + Path(i + 1, k - 1, n)                
                    Pst = matrix[i][k] + Path(i + 1, k, n)                    
                    Memo[(i, k)] = min(Pst, Psx)                    
                    return Memo[(i, k)]                
        Min = 10 ** 7        
        for k in range(0, len(matrix[0])):            
            CP = Path(0, k, len(matrix[0]))            
            if CP < Min:                
                Min = CP                
        return Min