leetcode-931-下降路径最小和

发表于 阅读次数： 本文字数： 593 阅读时长 ≈ 1 分钟
简介：leetcode-931-下降路径最小和

题目

https://leetcode.cn/problems/minimum-falling-path-sum/description/?envType=study-plan-v2&envId=dynamic-programming

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        m,n = len(matrix), len(matrix[0])
        lst = [[0 for j in range(n)] for i in range(m)]

        for i in range(n):
            lst[m-1][i] = matrix[m-1][i]

        for i in range(m-2,-1,-1):
            for j in range(n):
                if j==0:
                    lst[i][j] = matrix[i][j] + min(lst[i+1][j],lst[i+1][j+1])
                elif j==n-1:
                    lst[i][j] = matrix[i][j] + min(lst[i+1][j],lst[i+1][j-1])
                else:
                    lst[i][j] = matrix[i][j] + min(lst[i+1][j-1],lst[i+1][j],lst[i+1][j+1])

        # print(lst)
        return min(lst[0])