LeetCode 931. 下降路径最小和

原创

freesan44

修改于 2021-11-15 08:40:01

1900

修改于 2021-11-15 08:40:01

文章被收录于专栏：freesan44freesan44

题目地址(931. 下降路径最小和)

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

题目描述

给你一个 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 == matrixi.length

1 <= n <= 100

-100 <= matrixi <= 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(n^2)$

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python

数据结构

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python

数据结构

登录后参与评论

0 条评论

热度