华为 OD 训练营 · 题解精讲
LC64. 最小路径和
配套讲解：视频讲解 ↗
LC64. 最小路径和 视频地址：https://uha.xet.tech/s/2XAwTA
题目描述
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。
题目解析
解题思路
本题是典型的二维动态规划问题。由于每次只能向下或向右移动，到达位置 (i,j) 的路径必然经过其上方 (i-1,j) 或左方 (i,j-1)。因此可以定义 dp[i][j] 表示从左上角走到 (i,j) 的最小路径和，状态转移方程为：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
边界条件：第一行只能从左向右累加，第一列只能从上向下累加。
关键步骤
1. 初始化：创建 m × n 的 dp 数组，dp[0][0] = grid[0][0]。 2. 处理第一行：for i in range(1, n): dp[0][i] = dp[0][i-1] + grid[0][i] 3. 处理第一列：for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] 4. 填充剩余格子：双重循环遍历 i=1..m-1, j=1..n-1，按转移方程计算。 5. 返回结果：dp[m-1][n-1]
示意图（以 2×2 为例）：
grid: [1, 3] dp: [1, 4]
[1, 5] [2, 7] ← 7 = min(4,2) + 5复杂度分析
- 时间复杂度：
O(m×n)，需要遍历整个网格一次。 - 空间复杂度：
O(m×n)，使用了一个与输入网格同大小的二维dp数组。
参考代码
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# m 表示有多少行
m = len(grid)
# n 表示每一行有多少个元素，即 n 表示有多少列
n = len(grid[0])
# 设置二维数组 dp 用来储存每个位置的最优解
# dp[0][0] 表示第 0 行第 0 列的最优解
# dp[0][i] 表示第 0 行第 i 列的最优解
# dp[j][0] 表示第 j 行第 0 列的最优解
# dp[i][j] 表示第 i 行第 j 列的最优解
dp = [[0] * n for _ in range(m)]
# 初始化 dp[0][0]，由于只有一个元素
# 所以 dp[0][0] 的最优解就是 grid[0][0] 这个元素
dp[0][0] = grid[0][0]
# i 从 1 遍历到 n - 1
# 获取第 0 行中第 i 列的最优解
# 比如 grid[0] 为 [1,3,2...]
# 由于每次只能向下或者向右移动一步，此时只能向右移动一步
# 那么 dp[0][i] 依次为 [1,4,6...]
for i in range( 1 , n ):
# 所以对于只有一行的情况，当前位置的最优解等于前一列的最优解加上该列的值
dp[0][i] = dp[0][i-1] + grid[0][i]
# i 从 1 遍历到 n - 1
# 获取第 i 行中第 0 列的最优解
# 比如 grid 为
# [1,1,2.......]
# [5,2,2.......]
# [2,3,4.......]
# [..,..,..,...]
# 由于每次只能向下或者向右移动一步，此时只能向下移动一步
# 那么 dp[i][0] 就是
# [1,..........]
# [6,..........]
# [7,..........]
# [............]
for i in range( 1 , m ):
# 所以对于只有一列的情况，当前位置的最优解等于前一行的最优解加上该行的值
dp[i][0] = dp[i-1][0] + grid[i][0]
# 接下来从第 1 行到第 m - 1 行
# 从第 1 列到底 n - 1 列
# 填充二维数组 dp 里面的值
# dp[i][j] 表示第 i 行第 j 列的最优解
for i in range(1, m):
for j in range(1, n):
# 由于每次只能向下或者向右移动一步
# 位置 (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] 表示第 m - 1 行第 n - 1 列的最优解
# 返回这个结果即可
return dp[m-1][n-1]