[LeetCode] 931. Minimum Falling Path Sum

 Problem : https://leetcode.com/problems/minimum-falling-path-sum/

A classic DP problem.

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        dp = matrix[0][:]
        tmp = [0] * COLUMN
        
        for y in range(1, ROW):
            for x in range(COLUMN):
                tmp[x] = dp[x]
                
                if x - 1 >= 0:
                    tmp[x] = min(tmp[x], dp[x-1])
                    
                if x + 1 < COLUMN:
                    tmp[x] = min(tmp[x], dp[x+1])
                
                tmp[x] += matrix[y][x]
            
            dp, tmp = tmp, dp
        
        return min(dp)