网络异常，图片无法展示
|
题目地址(931. 下降路径最小和)
题目描述
给你一个 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,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
提示：
n == matrix.length n == matrix[i].length 1 <= n <= 100 -100 <= matrix[i][j] <= 100
思路
DP规划，存储【-1】数组的min内容，然后根据不同特殊条件进行遍历
代码
- 语言支持：Python3
Python3 Code:
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)
复杂度分析
令 n 为数组长度。
- 时间复杂度：O(n^2)O(n2)
- 空间复杂度：O(n^2)O(n2)
