title

problem link Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row. The next rows choice must be in a column that is different from the previous rows column by at most one.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]] Output: 12 Explanation: The possible falling paths are:

[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum is [1,4,7], so the answer is 12.

Constraints:

1 
-100 

solution

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        res = 0
        maxValue = sys.maxsize
        m, n = len(A), len(A[0])
        dp = [[maxValue for _ in range(n)] for _ in range(m)]
        dp[0] = A[0]
        for i in range(1, m):
            for j in range(0, n):
                for k in range(max(0, j - 1), min(n - 1, j + 1) + 1):
                    dp[i][j] = min(dp[i][j], A[i][j] + dp[i - 1][k])
        return min(dp[m - 1])