找一个二维数组比较复杂的题

题目描述：

给定一个二维数组，其中每个元素都是一个整数，求出从左上角到右下角的最短路径，每次只能向下或向右移动一格。

例如，给定以下二维数组：

[
[1,3,1],
[1,5,1],
[4,2,1]
]

则从左上角到右下角的最短路径为 1 → 3 → 1 → 1 → 1，总路径和为 7。

解题思路：

这是一道动态规划的经典问题。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从左上角出发到 (i,j) 位置的最短路径和。显然，dp[0][0] = grid[0][0]。

我们考虑如何更新 dp 数组。由于每次只能向下或向右移动一格，因此到达 (i,j) 位置的最短路径和，要么是从 (i-1,j) 向下走一步得到的，要么是从 (i,j-1) 向右走一步得到的。因此，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

最终，dp[m-1][n-1] 就是从左上角出发到右下角的最短路径和。

Python 代码实现：

class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
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]