OJ练习第135题——下降路径最小和

**OJ练习第135题——下降路径最小和**

**题目描述:**

给定一个 m x n 的网格 grid，其中每个单元格都有一个整数值。从左上角开始，向右移动到右上角的路径必须至少经过一次下降步骤（即，从一个更高的单元格移动到一个更低的单元格）。找到从左上角到右上角的最小路径和。

**示例:**

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]

输出：12解释：从左上角开始，下降路径为 [1,2,3] -> [4,5,6] -> [7,8,9]。最小路径和为1 +2 +3 +4 +5 =15。

**代码实现:**

def minPathSum(grid):
 """
 从左上角到右上角的最小路径和。
 Args:
 grid (list[list[int]]): m x n 的网格 Returns:
 int: 最小路径和 """
 # 行数 m = len(grid)
 # 列数 n = len(grid[0])
 # 初始化第一行的值 for i in range(1, n):
 grid[0][i] += grid[0][i-1]
 # 初始化第一列的值 for i in range(1, m):
 grid[i][0] += grid[i-1][0]
 # 从第二行开始，计算每个单元格的最小路径和 for i in range(1, m):
 for j in range(1, n):
 grid[i][j] += min(grid[i-1][j], grid[i][j-1])
 return grid[m-1][n-1]

# 测试用例grid = [[1,2,3],[4,5,6],[7,8,9]]
print(minPathSum(grid)) # 输出:15