931. 下降路径最小和
中等
281
相关企业
给你一个 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].length1-100
Solution
比较显然的dp。
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
col = [[0] * n for _ in range(2)]
if n == 1:
return sum(list(*matrix))
for i in range(m):
for j in range(n):
if j == 0:
col[(i + 1) % 2][j] = min(col[i % 2][j], col[i % 2][j + 1]) + matrix[i][j]
elif j == n - 1:
col[(i + 1) % 2][j] = min(col[i % 2][j], col[i % 2][j - 1]) + matrix[i][j]
else:
col[(i + 1) % 2][j] = min(col[i % 2][j - 1], col[i % 2][j], col[i % 2][j + 1]) + matrix[i][j]
return min(col[n % 2])但是还是学习一下官方题解对于判断分支的写法：
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 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: 深入分布式一致性：Raft 和 etcdRaft
分布式一致性是构建可靠的分布式系统的关键要素之一。为了确保数据的一致性和可用性，一致性算法的设计变得至关重要。在这篇博文中，我们将深入探讨两个与分布式一致性密切相关的主题：Raft 算法和 etcdRaft 存储系统。 Raft 算法：分布式一致性的基石 Ra…
