难度: Medium
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：一个机器人每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]] 输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100注意：本题与主站 64 题相同： https://leetcode-cn.com/problems/minimum-path-sum/
运行时间: 28 ms
内存: 18.3 MB
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
#其中dp(i, j)的值代表直到走到（i,j）的最小路径和
dp = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
#起点
if i == 0 and j == 0:
dp[i][j] = grid[i][j]
# 中间的点，可以从左边和上边过来
elif i != 0 and j != 0:
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
#只能从左边过来
elif i == 0 and j != 0:
dp[i][j] = grid[i][j] + dp[i][j-1]
#只能从上边过来
elif i != 0 and j == 0:
dp[i][j] = grid[i][j] + dp[i-1][j]
#print(dp) # grid =[[1,3,1],[1,5,1],[4,2,1]]
return dp[rows-1][cols-1]
此题解采用动态规划的方法来求解最小路径和问题。定义一个二维数组 dp，其中 dp[i][j] 表示从左上角 (0, 0) 到位置 (i, j) 的最小路径和。初始化 dp[0][0] 为起点的值 grid[0][0]。对于网格的其他位置，如果位置在第一行，只能从左边的位置到达；如果位置在第一列，只能从上面的位置到达；对于其他位置，则需要考虑从左边或上面到达的路径中哪一条的路径和更小。最后，dp数组的最右下角的值即为整个网格的最小路径和。
时间复杂度: O(m * n)
空间复杂度: O(m * n)
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
# dp[i][j] 代表从 (0,0) 到 (i,j) 的最小路径和
dp = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
if i == 0 and j == 0: # 起点初始化
dp[i][j] = grid[i][j]
elif i != 0 and j != 0: # 可以从左边或上边到达
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
elif i == 0 and j != 0: # 第一行，只能从左边到达
dp[i][j] = grid[i][j] + dp[i][j-1]
elif i != 0 and j == 0: # 第一列，只能从上面到达
dp[i][j] = grid[i][j] + dp[i-1][j]
return dp[rows-1][cols-1]
在这个问题中，每个单元格的最小路径和依赖于其左侧和上方的单元格的值（因为只能从左侧或上方到达）。因此，从左到右，从上到下的顺序确保在计算 dp[i][j] 时，dp[i-1][j]（上方）和 dp[i][j-1]（左侧）都已经被计算过，满足动态规划的依赖顺序。如果反向或交叉填充，会造成依赖的单元格还未被计算，从而无法正确计算当前单元格的值。
代码中虽然初步只设置了 dp[0][0]，但在遍历过程中对第一行和第一列的每个单元格都进行了单独的处理。对于第一行，每个单元格的值只依赖于其左边单元格的值；对于第一列，每个单元格的值只依赖于其上方单元格的值。这样的处理方式动态地在循环中初始化了第一行和第一列，无需事先设置整行或整列。
可以通过添加额外的辅助行和列来简化代码。例如，可以设置 dp 数组的大小为 (rows+1) x (cols+1)，并初始化辅助行和辅助列的值为极大数，除了 dp[1][1]，这样就可以统一处理所有的单元格更新逻辑。每个单元格 dp[i][j] 都可以通过同样的方式计算，即 dp[i][j] = grid[i-1][j-1] + min(dp[i-1][j], dp[i][j-1])。这种方法减少了边界条件的特殊处理，使代码更加整洁。