题目描述
网格每格是非负代价，每步只能向右或向下，求从左上角到右下角路径上代价之和的最小值。
思路解析
最直接的想法是把所有「右/下」走法都列出来、各算一次总代价、取最小。可路径数随网格指数增长，而且很多路前半段是重叠的，被一遍遍重复求和，太慢。
转折：用 dp[i][j] 记「走到 (i,j) 的最小代价」，每格只算一次。一个格子只能从上面或左边来，那当然挑代价小的那条接上：dp[i][j] = min(dp[i−1][j], dp[i][j−1]) + grid[i][j]。取 min 的那一刻就把较大的那条路丢掉了。第一行、第一列只有一条路，前缀累加即可。
建表 · 起点：建一张 3×3 的 dp 表（行列数全程不变）。起点 dp[0][0] 就等于它自己的代价 grid[0][0]=1。其余先空着。
第一行 · 只能向右累加：第一行头顶没格子，只能一路向右，所以是前缀和：1、1+3=4、4+1=5。这一行不用取 min（没有别的路可选）。
第一列 · 只能向下累加：第一列左边没格子，只能一路向下：1、1+1=2、2+4=6。边界铺好了，下面开始对内部格子取 min。
填 (1,1) · 取较小的那条：(1,1) 代价 5，可从上面（dp=4）或左边（dp=2）来。取 min 挑左边的 2，把上面那条 4 丢掉——这就是核心的「取小、弃大」分支。dp = 2 + 5 = 7。
填 (1,2) · 这次上比左小：(1,2) 代价 1，从上面（dp=5）或左边（dp=7）来。这回反过来——上面 5 更小，丢掉左边的 7。dp = 5 + 1 = 6。可见每格选哪条全看谁小，不固定。
填 (2,1) · 取左：(2,1) 代价 2，从上面（dp=7）或左边（dp=6）来，取小挑左边 6，丢掉上面 7。dp = 6 + 2 = 8。
右下角 · 取上：终点 (2,2) 代价 1，从上面（dp=6）或左边（dp=8）来，取小挑上面 6。dp = 6 + 1 = 7，正是那条 1→3→1→1→1 的最小路径和。
答案：右下角 dp[2][2] = 7 就是答案。整张表每格都在「上、左」里挑了代价更小的一条接上来。
同一张网格 DP 表，换聚合方式就解不同题：计数用加法（不同路径），求最小用 min（本题），求最大用 max。骨架一样，只改那一个聚合符。
参考代码（Python）
1def minPathSum(self, grid):
2 m, n = len(grid), len(grid[0])
3 dp = [[0] * n for _ in range(m)]
4 dp[0][0] = grid[0][0]
5 for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # 第一行：只能从左累加
6 for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] # 第一列：只能从上累加
7 for i in range(1, m):
8 for j in range(1, n):
9 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] # 取较小那条
10 return dp[m-1][n-1]复杂度分析
- 时间复杂度：O(m × n) —— 每个格子只做一次 min 和一次加法
- 空间复杂度：O(m × n) —— 一张 m×n 的 dp 表，可压成一行 O(n)
套路模板
记住骨架：第一行/列前缀累加、内部 min(上,左)+当前格。求最大路径和就把 min 换 max，三角形最小路径和（LC120）也是它的变形。
1dp[0][0] = grid[0][0]
2for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # 第一行前缀
3for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] # 第一列前缀
4for i in range(1, m):
5 for j in range(1, n):
6 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
7return dp[m-1][n-1]易错点
- 错误写法：第一行/列也套 min(dp[i-1][j], dp[i][j-1]) 公式 → 正确写法：第一行、第一列单独前缀累加（第一行没有「上」、第一列没有「左」，硬套 min 会取到 dp 还是 0 的不存在格，把最小值错误地压成 0）
- 错误写法：dp[i][j] = min(上, 左) 之后忘了 + grid[i][j] → 正确写法：min(上, 左) 后必须再加当前格代价（路径和要算上当前格自己的代价，漏加会少算整整一格）
- 错误写法：min 写成 max → 正确写法：求最小路径和用 min（聚合符是这类题唯一的区别，写错就求成了最大代价路径）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。