难度: Medium
给你一个 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 <= n <= 100-100 <= matrix[i][j] <= 100运行时间: 37 ms
内存: 16.9 MB
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
n=len(matrix)
for i in range(1,n):
for j in range(n):
if j==0:
matrix[i][0]+=min(matrix[i-1][0],matrix[i-1][1])
elif j==n-1:
matrix[i][-1]+=min(matrix[i-1][-1],matrix[i-1][-2])
else:
matrix[i][j]+=min(matrix[i-1][j],matrix[i-1][j-1],matrix[i-1][j+1])
return min(matrix[-1])
这个解题思路采用动态规划方法。它在原矩阵上进行修改，通过逐行更新来得到最小的下降路径和。具体地，对于矩阵中的每个元素，它将当前元素值更新为自身加上其正上方，左上方和右上方三个可能的前驱元素中的最小值。对于每行的第一个和最后一个元素，因为不存在左上或右上元素，所以只考虑可行的前驱元素。整个过程重复直到矩阵的最后一行，然后返回最后一行中的最小值作为结果。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
n = len(matrix) # 矩阵的行数或列数
# 遍历从第二行开始到最后一行
for i in range(1, n):
for j in range(n): # 遍历当前行的每一列
if j == 0:
# 如果是第一列，只能从上面或右上来
matrix[i][0] += min(matrix[i-1][0], matrix[i-1][1])
elif j == n-1:
# 如果是最后一列，只能从上面或左上来
matrix[i][-1] += min(matrix[i-1][-1], matrix[i-1][-2])
else:
# 中间的列可以从上面，左上或右上来
matrix[i][j] += min(matrix[i-1][j], matrix[i-1][j-1], matrix[i-1][j+1])
# 返回最后一行中的最小值
return min(matrix[-1])
可以通过添加一个哨兵（虚拟）行和列的方式来简化边界条件的处理。具体方法是在原始矩阵的每一行的开始和结束添加一个很大的值（例如Integer.MAX_VALUE）。这样，对于每个元素，无论是在边界还是中间，都可以统一地考虑左上、正上、右上三个位置，而不需要进行特殊的边界判断。这样的改动可以使代码更简洁，但可能会轻微增加空间和时间的开销。
该算法可以处理所有的 n x n 矩阵，包括 n=1 的情况。当矩阵只有一行（n=1）时，由于不存在任何下降路径，算法将直接返回这一行（也是唯一的行）中的最小值。这是因为循环从第二行开始，对于仅有一行的矩阵，循环体内的代码根本不会执行。
是的，该算法在计算每个元素时，都考虑了从左上、正上和右上三个方向下来的可能性。这意味着所有的斜向下降路径也被考虑在内。因此，算法最终返回的最后一行中的最小值确实是考虑了所有可能的下降路径。
算法依然有效即使矩阵中包含负数。动态规划的本质是通过局部最优解来构建全局最优解，所以即便是元素值为负，算法也能够正确地处理并累加这些值。负数会影响到路径和的计算，因为它们会减小累积的和，这可能导致选择包含负数的路径作为最优路径。