给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

 

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径

示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径

 

提示：

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

思路分析

标准的多点dfs或者二维dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # 多点dfs
    # 自上而下、自下而上都可以 + 记忆化搜索
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        
        @cache
        def dfs(x,y):
            ans = matrix[x][y]
            if x == n-1 :
                return ans
            res = inf
            for dy in range(y-1,y+2):
                if dy >= 0 and dy <= n-1:
                    res = min(res,dfs(x+1,dy))
            return  ans+res

        mi = inf 
        n = len(matrix)
        for i in range(n):
            # 从第一行进行dfs
            mi = min(mi,dfs(0,i))
        return mi

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:
        #滚动数组 也可以二维数组
        n = len(matrix)
        dp = [[0]*n for i in range(2)]
        # dp = [[0]*n for i in range(n)]
        dp[0] = [x for x in matrix[0]]
        for x in range(1,n):
            for y in range(n):
                res = inf
                if y-1 >= 0:
                    res = min(res,dp[0][y-1])
                if y+1 < n:
                    res = min(res,dp[0][y+1])
                res = min(res,dp[0][y])
                dp[1][y] = res + matrix[x][y]
            dp = [dp[1],[0]*n]
            # 滚动数组需要重复利用空间
        return min(dp[0])

官解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        dp = [matrix[0]]
        n = len(matrix)
        for i in range(1, n):
            cur = [0] * n
            for j in range(n):
                mn = dp[-1][j]
                if j > 0:
                    mn = min(mn, dp[-1][j - 1])
                if j < n - 1:
                    mn = min(mn, dp[-1][j + 1])
                cur[j] = mn + matrix[i][j]
            dp.append(cur)
        return min(dp[-1])

复杂度分析

时间复杂度：O()，需要计算每个坐标的和最小下降路径。
空间复杂度：O()，需要记录每个坐标的和最小下降路径。
因为每个坐标的和最小下降路径仅与上一行有关，因此可以使用滚动数组，使得空间复杂度降低为 O()。