【每日一题】931 . 最小下降路径总和

**最小下降路径总和**

**问题描述**

给定一个由整数组成的二维数组 `grid`，其中每个元素代表一个点。我们需要找到从左上角到右下角的最短路径的总和，这条路径只能向右或向下移动。

**示例**

假设 `grid = [[1,2,3],[4,5,6],[7,8,9]]`，则最小下降路径总和为15，因为从左上角到右下角的最短路径是：1 ->2 ->3 ->6 ->9。

**解决方案**

我们可以使用动态规划来解决这个问题。首先，我们需要定义一个二维数组 `dp`，其中 `dp[i][j]` 表示从左上角到 `(i, j)` 的最短路径总和。

def minPathSum(grid):
 m, n = len(grid), len(grid[0])
 # 初始化 dp 数组 dp = [[0]*n for _ in range(m)]
 # 初始化第一行和第一列 for i in range(m):
 dp[i][0] = grid[i][0] + (dp[i-1][0] if i >0 else0)
 for j in range(n):
 dp[0][j] = grid[0][j] + (dp[0][j-1] if j >0 else0)
 # 填充 dp 数组 for i in range(1, m):
 for j in range(1, n):
 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
 return dp[m-1][n-1]

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