64. 最小路径和 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/minimum-path-sum/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个包含非负整数的 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.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
题目详细分析
- 数据范围：m, n <= 200，网格值范围为 [0, 200]。O(m * n) 的 DP 足够。
- 核心约束：只能向右或向下，不能向左或向上。网格值非负，意味着路径和不会随着路径缩短而减少。
- 边界条件：左上角是起点，路径和 = grid[0][0]；第一行只能从左边来；第一列只能从上面来。
- 隐藏条件：由于非负约束，贪心思想（局部最小）不一定等于全局最小，必须用 DP 保证全局最优。
小白版直白理解
你要从地图左上角走到右下角，每经过一个格子要付”过路费”（格子里的数字），每次只能往右或往下走。你想找一条过路费总和最小的路线。这就像玩游戏时规划最省钱的路线——到达某个路口的最小费用 = 这个路口的过路费 + min(从左边来的总费用, 从上面来的总费用)。
解题思路
思路一：二维 DP（推荐）
核心洞察：到达 (i,j) 的最小路径和 = grid[i][j] + min(从上方来的路径和, 从左方来的路径和)。第一行只能从左来，第一列只能从上来。
DP 五步法：
- dp 定义：
dp[i][j]表示到达 (i,j) 的最小路径和 - 递推公式：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) - 初始化：
dp[0][0] = grid[0][0]；第一行：dp[0][j] = dp[0][j-1] + grid[0][j]；第一列：dp[i][0] = dp[i-1][0] + grid[i][0] - 遍历顺序：从左到右，从上到下
- 举例验证：grid=[[1,3,1],[1,5,1],[4,2,1]] → dp[0]=[1,4,5]; dp[1]=[2,7,6]; dp[2]=[6,8,7] ✓
def minPathSum(grid):
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# 初始化第一行
for j in range(1, n):
dp[0][j] = dp[0][j - 1] + grid[0][j]
# 初始化第一列
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + grid[i][0]
# DP 递推
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[m - 1][n - 1]思路二：原地修改（空间 O(1)）
直接在原 grid 上修改，不申请额外空间。
def minPathSum(grid):
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
elif i == 0: # 第一行
grid[i][j] += grid[i][j - 1]
elif j == 0: # 第一列
grid[i][j] += grid[i - 1][j]
else: # 中间格子
grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
return grid[m - 1][n - 1]思路三：一维 DP（滚动数组优化）
与不同路径类似，用一维数组滚动更新。
def minPathSum(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # 每行第一个只能从上面来
for j in range(1, n):
# dp[j] 来自上方（旧值），dp[j-1] 来自左方（新值）
dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
return dp[-1]易错点
- 初始化顺序：必须先初始化 dp[0][0] 和第一行、第一列，再递推中间部分。
- 原地修改副作用：如果外部需要保留原 grid 数据，不要用原地修改。
- 一维 DP 的 dp[0] 处理：每行开头
dp[0] += grid[i][0]不能忘。 - 索引越界：创建定长数组后，小心 m, n 为 1 的边界情况。
框架提炼
二维最值 DP 模板（依赖上方和左方）：
def grid_path_min(grid):
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
# 初始化第一行第一列
dp[0][0] = grid[0][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
# 递推
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]这种”左上到右下”的网格 DP 结构非常通用，核心是处理第一行和第一列的边界。
关联题目
- 62-不同路径 — 计数版本，网格结构相同，递推从取 min 变加法
- 120-三角形最小路径和 — 类似网格 DP，三角形结构需从下往上遍历
- 931-下降路径最小和 — 格子可以向下、左下、右下三种移动