931. Minimum sum of descent paths

Leetcode-cn.com/problems/mi…

Topic describes

Given a matrix of square integers of n x n, find and return the minimum sum of the descending paths through the matrix.

The descent path can start with any element in the first row and select one element from each row. The element selected in the next row is at most one column away from the element selected in the current row (that is, the first element directly below or diagonally to the left or right). Specifically, the next element of the position (row, col) should be (row + 1, col-1), (Row + 1, col), or (Row + 1, col + 1).

Example 1: input: matrix = [[2,1,3],[6,5,4],[7,8,9]] output: 13 explanation: the following are the two and smallest descent paths, highlighted in bold + italics: ,1,3,1,3 [[2], [[2], [6,5,4],,5,4 [6], [7,8,9]],8,9 [7]] example 2: input: matrix = [19,57 [-], [- 40-5]] output: 59: The following is one and the smallest descent path, indicated in bold + italics: [[-19,57], [-40,-5]] Example 3: Input: matrix = [[-48]] Output: -48Copy the code

Tip:

n == matrix.length n == matrix[i].length 1 <= n <= 100 -100 <= matrix[i][j] <= 100

Train of thought

DP planning, storage [-1] array min content, and then according to different special conditions for traversal

code

  • Language support: Python3

Python3 Code:


class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) - >int:
        length = len(matrix)
        # Build DP matrix to record
        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 specificity of the 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)

Copy the code

Complexity analysis

Let n be the length of the array.

  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)