LeetCode 931. Descent path min sum

Title address (931. The descent path is the smallest and )

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

Title Description

To give you one n x n Of square An array of integers  matrix , Please find out and return through matrix The descent path Of Minimum and .

descent path You can start with any element in the first line , And select an element from each row . The element selected in the next row is at most one column apart from the element selected in the current row （ That is, the first element directly below or diagonally left or right ）. say concretely , Location (row, col) The next element of should be (row + 1, col - 1)、(row + 1, col) perhaps (row + 1, col + 1) .

 Example  1：



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

 Output ：13

 explain ： Here are the two and smallest descent paths , Bold with + Italic annotation ：

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

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

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

 Example  2：



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

 Output ：-59

 explain ： Here is a and minimum descent path , Bold with + Italic annotation ：

[[-19,57],

 [-40,-5]]

 Example  3：



 Input ：matrix = [[-48]]

 Output ：-48

 

Tips ：

n == matrix.length

n == matrixi.length

1 <= n <= 100

-100 <= matrixi <= 100

Ideas

DP planning , Storage 【-1】 Array of min Content , Then traverse according to different special conditions

Code

• Language support ：Python3

Python3 Code:

class Solution:

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

        length = len(matrix)

        #  structure DP Matrix for recording 

        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

                ## Set the particularity of boundary conditions 

                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)

** Complexity analysis **

Make n Is array length .

• Time complexity ：$O(n^2)$
• Spatial complexity ：$O(n^2)$