LeetCode 931. 下降路径最小和

示例 1：



输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]

输出：13

解释：下面是两条和最小的下降路径，用加粗+斜体标注：

[[2,1,3],      [[2,1,3],

 [6,5,4],       [6,5,4],

 [7,8,9]]       [7,8,9]]

示例 2：



输入：matrix = [[-19,57],[-40,-5]]

输出：-59

解释：下面是一条和最小的下降路径，用加粗+斜体标注：

[[-19,57],

 [-40,-5]]

示例 3：



输入：matrix = [[-48]]

输出：-48

 

class Solution:

    def minFallingPathSum(self, matrix: List[List[int]]) -> int:

        length = len(matrix)

        # 构建DP矩阵进行记录

        dp =  [[0]*length for i in range(length)]

        dp[0] = matrix[0]

        for i in range(1,length):

            for j in range(length):

                val = 0

                ##设置边界条件的特殊性

                if j == 0:

                    val = min(dp[i-1][j],dp[i-1][j+1])

                elif j == length-1:

                    val = min(dp[i - 1][j], dp[i - 1][j - 1])

                else:

                    val = min(dp[i - 1][j-1],dp[i - 1][j], dp[i - 1][j + 1])

                dp[i][j] = val+matrix[i][j]

        return min(dp[-1])



if \_\_name\_\_ == '\_\_main\_\_':

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

    matrix = [[-19, 57], [-40, -5]]

    res = Solution().minFallingPathSum(matrix)

    print(res)