直接说结论：这是一道拉开差距的题。同样是“最小路径和”，有人只会背二维DP模板，有人能顺手写出滚动数组加原地修改，面试官对后者的评价完全不一样。力扣hot100榜单里把它放在第95位，难度标注为中等，但我觉得它的含金量被很多人低估了——它几乎是动态规划从入门到进阶最顺滑的一道过渡题，所有该踩的坑、该懂的优化、该防的边界，都浓缩在一个看似简单的网格里。
题目本身读起来不复杂：给你一个 m×n 的非负整数网格 grid，从左上角走到右下角，每次只能向下或者向右移动一步，求路径数字总和的最小值。就这几十个字，背后能拆出DFS暴力搜索、二维动态规划、一维滚动数组、原地修改四种解法，还能顺便引出打印路径、变种题如不同路径、最大正方形等一连串面试追问。
这篇文章我会从头到尾走一遍完整思考过程：先算暴力搜索为什么必挂，再推DP的状态定义和转移方程，然后讲滚动数组怎么压空间，最后补上原地修改和一系列实战中才遇得到的坑。不光是给代码，我会把每一步“为什么这么做”都讲清楚，方便你面试时经得起追问。
1. 为什么这道题值得反复刷：先看题面再谈套路
先说个现象。很多人刷题有个误区：看到“最小路径和”五个字，脑子里直接蹦出“dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])”，然后背模板AC，自我感觉良好，过两天再遇到就忘得一干二净。原因很简单——没有理解转移方程从哪里来，也没搞懂边界条件为什么那样初始化。
这道题在我看来最适合三类人反复刷。第一类是刚学动态规划的新手，此前只做过爬楼梯、斐波那契这类一维问题，需要一道二维题目来建立状态表的概念。第二类是准备面试的求职者，拿这一道题串起多种解法，用最少的题量覆盖最多的考点。第三类是刷题平台复刷党，第一次只会二维DP，但不知道如何压到一维，更不知道原地修改怎么写，二次刷题会有新的收获。
还有一个重点必须强调：题面中的“非负整数”和“每次只能向下或向右移动”决定了整套解法方向。正因为数字非负，才不会有负权回路，动态规划能保证正确性；正因为路径方向固定，每个格子的状态只依赖左上方向，递推关系才清晰可控。换个场景说，如果允许上下左右走，这道题就变成图论最短路径问题，得用 Dijkstra 或带权BFS，完全是另一套思路了。
我自己的建议是：刷这道题不要满足于AC，至少把下面三个问题用嘴讲清楚——为什么贪心不行？为什么状态转移只用两个方向？空间还能不能优化？能把这三个问题答明白，这道题就算真正吃透了。
2. 暴力搜索为什么必然超时：先算一笔复杂度账
很多第一次做题的人会想：既然只能向下和向右，路径总数虽然多，但用DFS把所有路径走一遍，总能找出最小和吧？这个思路在 m、n 很小的时候确实能跑通，但先算一笔账，你就知道为什么必须换思路。
从 (0,0) 到 (m-1,n-1)，由于只能向右和向下，需要走 (m-1)+(n-1)=m+n-2 步，其中正好有 m-1 步向下、n-1 步向右。路径数量等于组合数 C(m+n-2, m-1)。当网格是 10×10 时，路径数约 48620 条，DFS还能接受；但到了 15×15，路径数约 40116600 条，4000万条路径已经明显卡顿；到了 30×30，路径数突破了 3×10^16，这个量级暴力搜索连一份样例都跑不完。
我在本地实测过一个朴素的DFS递归实现，输入的网格是 100×100，等了整整几分钟都没出结果，最后还是手动终止了。递归深度方面，100×100 的网格递归深度接近 200 层，虽然不至于爆栈，但时间上完全不可接受。
所以这道题的意义就在这里：暴力枚举路径的方案是指数级复杂度，而动态规划把问题拆成 m×n 个格子的状态，每个格子只计算一次，复杂度直接降到多项式级。理解这个对比，你才能明白DP的本质不是“玄学套路”，而是把重复计算的子问题结果存下来，用空间换时间。
3. 二维DP：从状态定义到状态转移
3.1 状态定义
动态规划第一步永远是想清楚 dp 数组代表什么含义。这里我定义 dp[i][j] 表示从左上角 (0,0) 走到当前格子 (i,j) 的最小路径和。
为什么这样定义？因为题目问的就是“从左上到右下的最小路径和”，把相同结构的问题一层层分解到每个子格子上，最终 dp[m-1][n-1] 就是答案。这种定义方式还有一个好处：二维网格天然对应二维数组，不需要额外做状态压缩设计，是最直接、最不容易出错的建模方式。
3.2 状态转移方程
要走到 (i,j)，上一步只能是两个位置：上方 (i-1,j) 或者左方 (i,j-1)。由于路径只能向下或向右，不可能从其他方向进来。因此，当前格子的最小路径和就等于“到达上方格子的最小路径和”和“到达左方格子的最小路径和”中较小的那一个，再加上当前格子本身的值，即：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
这个方程用生活化的方式来理解：你从家出发去某个目的地，每次都只能往右或往下走，路费由经过的地板砖价格总和决定。到达每个房间的最省钱方案，一定是从两个入口中花钱较少的那一侧进来，再付清当前房间的“入场费”。
3.3 边界初始化
边界是最容易翻车的地方。dp[0][0] 是起点，它的最短路径就是 grid[0][0] 本身，不需要比较任何前驱状态。第一行的格子无法从上方过来，所以 dp[0][j] 只能从左往右累加；第一列的格子无法从左方过来，所以 dp[i][0] 只能从上往下累加。这三条边界不处理，直接套用转移方程，要么出现数组越界，要么答案错误。
这里分享一个我见过的坑：有些教程喜欢用“dp数组多开一圈并用0做哨兵”的方式处理边界，把 dp[0][j] 和 dp[i][0] 预设为 0，然后统一转移。这种做法在“不同路径”里可行，因为那是求方案数，哨兵0是合理的；但在“最小路径和”里，哨兵0会把边界路径的最小值错误地拉成0，导致第一行第一列答案全部错乱。所以这道题别偷懒，老老实实显式初始化边界最稳妥。
3.4 二维DP完整实现
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] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) return dp[-1][-1]代码逻辑非常简单：先初始化起点、第一行、第一列，然后从 (1,1) 开始按行填充 dp 表。两层循环嵌套，每个格子只计算一次。时间复杂度 O(mn)，空间复杂度 O(mn)。
3.5 复杂度分析与优化意识
二维DP版本的复杂度已经是“可接受”范畴，但它消耗了和原网格同样大小的额外空间。在力扣平台上，200×200 的网格倒不算什么内存压力；但如果把它放到真实业务场景，比如地图寻路或图像处理中，网格变成 5000×5000，那么 2500 万个 int 的空间就会开始让人肉疼。这也是为什么后续要讨论空间优化——面试官未必关心你 AC，但一定关心你能不能进一步压内存。
4. 空间优化：把二维表压成一行
4.1 为什么 dp 表可以只保留一行
观察转移方程，dp[i][j] 只依赖两个值：上方 dp[i-1][j] 和左方 dp[i][j-1]。这意味着按行从上到下扫描时，计算第 i 行只需要第 i-1 行的数据，以及当前行左侧已经算好的数据。更早的历史行根本不会再被用到。
我打一个比方：你在做考勤统计，每个员工的薪资只取决于自己上一级部门汇总和他自己左边同事的汇总，你只需要手里拿着一张当前轮次的员工表，完全不需要把公司历年的工资册全背在身上。这就是滚动数组的思想。
算法里给出一维数组 dp[j]，它是“当前正在处理的行”的状态。更新前，dp[j] 存储的是上一行第 j 列的值；更新后，dp[j] 变成当前行第 j 列的值。一旧一新替换，循环往复，最终整个网格只使用一个长度为 n 的数组。
4.2 一维滚动数组完整实现
class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) dp = [0] * n dp[0] = grid[0][0] for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] for i in range(1, m): dp[0] = dp[0] + grid[i][0] for j in range(1, n): dp[j] = grid[i][j] + min(dp[j], dp[j-1]) return dp[-1]这段代码里有几个关键点必须注意。第一，先单独初始化第一行的 dp 数组，因为第一行只能从左往右累加。第二，进入下一行前，手动更新 dp[0]，因为第一列只能从上往下累加，它不依赖任何左侧值。第三，在内层循环中，等号右侧的 dp[j] 是上一行的内容，而 dp[j-1] 在本行中已经被更新为当前行的内容，两者一旧一新，混用是滚动数组的核心理念。
4.3 为什么不能写错更新顺序
如果先更新 dp[0]，再进入内层循环，顺序是正确的；如果反过来，先循环 j 再处理 dp[0]，那么第一列的所有值都会沿用上一行，彻底算错。更常见的一个错误是，内层循环写成从左到右自然没问题，但如果你写成从右到左的倒序，就会让 dp[j-1] 还是旧值，丢失当前行左侧的新状态，答案变成一团乱麻。
所以滚动数组的维护顺序，本质上就是在维护“数据依赖的时序”。这也是面试官真正想考察的点：代码形式谁都会模仿，但你能不能解释清楚为什么这里必须从左到右更新？能，就说明你理解了DP的空间复用。
4.4 空间复杂度与进一步优化
一维滚动数组的空间复杂度从 O(mn) 降到 O(n)。如果网格是 1000×1000，内存从 100万个值降到 1000个值，这个差距是实打实的。再深入一步，如果 n 远大于 m，可以先转置网格或交换行列，让滚动数组使用较小的维度，进一步减少内存占用。虽然这道题的测试用例用不上，但在真实项目中处理超宽网格时会非常实用。
5. 原地修改：再省掉一整块额外数组
5.1 覆盖数据的安全性判断
滚动数组已经能把空间压到 O(n)，那还能不能再压？能——如果题目允许修改原数组，直接在 grid 上原地计算，空间可以降到 O(1) 的额外空间。
判断能否原地修改的唯一标准是：当前格子被覆盖后，它的原数据是否还会被后面的计算所依赖。分析一下依赖关系：计算 grid[i][j] 时，只会读取 grid[i-1][j] 和 grid[i][j-1]。按行从上到下、从左到右扫描时，当到达 (i,j) 时，(i-1,j) 在上一步已经处理完，未来不会再读它的原值；同理，(i,j-1) 在当前行前面刚被处理完，原值也不会再被使用。所以覆盖是安全的。
5.2 原地修改代码
class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) for i in range(1, m): grid[i][0] += grid[i-1][0] for j in range(1, n): grid[0][j] += grid[0][j-1] for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i-1][j], grid[i][j-1]) return grid[-1][-1]这段代码和二维DP版本几乎一模一样，区别只是把 dp 表替换成 grid 本身。用这个方案时我建议你思考一个面试追问：如果改成按列扫描，覆盖顺序需要怎么调整？答案是改为先初始化第一列，每列从上到下扫描，转移方程变成 grid[i][j] += min(grid[i][j-1], grid[i-1][j])，依赖顺序仍然满足。这本质上是同一个DP在不同遍历顺序下的变体。
5.3 原地修改的代价
原地修改不是没有代价。它会破坏原始输入，如果后续还需要用原始 grid 做其他计算，这个方案就不可行。所以在写代码前，先想清楚题目的要求和工程场景中的约束。力扣通常不关心你改不改输入，但真实项目中，传一个列表进函数，出来整个列表变了，调用方往往会很崩溃。
6. 边界条件与常见陷阱
6.1 单行或单列矩阵
当 m=1 时，整个网格只有一行，路径被锁死在一条水平线上，答案必定是第一行的累加和。当 n=1 时，路径只有垂直一条线，答案是第一列的累加和。这两种情况在二维DP版本里靠两个初始化循环处理；在滚动数组版本里，靠一行初始化和每行只更新 dp[0] 来处理。我自己测试过所有解法在这些边界下的表现，输出都是正确的，前提是你不能跳过硬编码的边界初始化。
6.2 全零网格与 U 形路径
如果 grid 里的数字全是 0，最小路径和当然是 0。但千万别觉得这种用例简单，它恰恰能暴露“哨兵0初始化”类方案的错误。一旦把 dp 表的第0行第0列预设为0，然后在转移时做 min 比较，某些路径会错误地把0当成一条合法的更短路径混进来。所以这道题的边界处理，一定要建立在“真实边界值”之上，而不是依赖哨兵默认值。
6.3 数值溢出问题
题目说数字是非负整数，但没说范围上限。我测算过，如果网格是 200×200，每个格子都是 100000，那么最大路径和大约是 200×200×100000=4×10^9，超过 32 位 int 的 2^31-1 上限。Python 自然没有溢出问题，但如果你用 Java 或 C++，一不留神就会 WA 或者出现诡异的负数结果。建议要么用 long，要么先根据题目约束估算最大和，再决定 dp 数组的类型。
6.4 不能贪心的原因
面试官经常会追问：每一步都选数值最小的格子走，不就行了吗？为什么还要DP？答案是贪心只看局部，而最小路径和问题里，局部最优并不能保证全局最优。举个例子，一个 3×3 网格，第一行第一列是 1，右侧是 100，下方是 1；第一行第二列往下走是1，但后续累加可能比直接向右更贵或更便宜，这取决于远端路径。贪心过早做出选择，放弃了另一个方向上“前期略贵但后期全便宜”的可能性，所以必须枚举所有状态。
7. 常见问题与排查技巧实录
7.1 两行滚动数组的初始化偏差
我自己第一次用两行数组（即保留 prev 和 curr 两行）实现时，犯了一个典型错误：把第一行当成“上一行”直接参与转移，却没有给 prev 初始化真实值，导致前几列的结果被初始值污染。排查了很久才发现问题是 init 阶段缺了第一行独立累加的逻辑。如果同学也写两行版本，我建议在一开始就把第一行单独填好，而不是把它放进通用循环里。
7.2 一维数组新旧值混用
一维滚动数组最折磨人的一点就放在这里：dp[j] 在更新前是旧值，更新后是新值，而内层循环里 dp[j] 的取值完全取决于上一轮 j 是否已经处理过。我见过不止一个同学写完代码后自己推导，怎么推都觉得 min(dp[j], dp[j-1]) 里的 dp[j]-1 是旧值，然后怀疑代码逻辑。我的建议是画一个 2 行 5 列的小表格，手动把每轮更新前后的一维数组状态写出来，模拟三列就能彻底理解。
7.3 原地修改跟调用方数据冲突
实战中踩过的第三个坑：写算法时原地修改 AC 了，但到公司项目里复用这段逻辑时，传进去的网格后面还要用原值，结果全被覆盖了。所以我现在的习惯是：在接口设计里明确标注参数会不会被修改，或者干脆非必要不原地修改。这个习惯其实也是面试官喜欢看到的工程素养。
7.4 打印最短路径的追问
如果题目要求输出对应的具体路径，而不是只求最小和，怎么办？我的方案是多开一个 parent 或 direction 矩阵，在每次状态转移的同时，记录当前格子是从上方还是左方到来。计算完成后，从终点反向回溯到起点，就能还原整条路径。复杂度仍然是 O(mn)，但空间会额外增加一个方向矩阵。这个扩展我在面试前专门练过，应对追问很有帮助。
8. 延伸：从这道题抽象出的DP模板
看完了最小路径和的全部解法，我再分享一个可以用来套用一系列题目的思考模板。凡是从网格左上到右下，求路径和、路径数、路径可行性的DP题，都适合用下面四步来分析：
- 定义状态：明确 dp[i][j] 表示到达当前格子的某种指标，是要最小和、方案总数，还是可行性。
- 找转移关系：看题目允许从哪些方向进入当前格子，用 min、max 或加法组合这些来源状态。
- 处理边界：单独给起点、第一行、第一列设定初始值，别依赖哨兵默认值。
- 确认遍历顺序：保证计算 dp[i][j] 时，所有依赖的 dp 值都已经被计算出来。
拿这个模板去套几道力扣经典题，你会体会到同一套思路的威力。“不同路径”的转移是 dp[i][j] = dp[i-1][j] + dp[i][j-1]，边界是第一行第一列全为1法；“不同路径 II”在转移时先判断当前格子是否是障碍物，是则置0；“最大正方形”则是用 dp[i][j] 维护以当前点为右下角的最大边长，转移为 min 加1，题材看似完全不同，但骨架没变。
所以这道题的价值不仅在于它本身，更在于它是你建立网格DP思维的第一块稳固基石。刷完它，再回头做其他网格类DP题，你会发现自己不再是背公式，而是真的在“推导状态”。
个人体会
我这道题前前后后刷了三遍，每一遍都有新体会。第一遍用二维DP过了，觉得不过如此；第二遍被面试官追问空间优化，临时吭哧吭哧写出了滚动数组，但讲不清楚为什么能覆盖；第三遍把原地修改、边界陷阱、打印路径全部吃透之后，才敢说自己真的会了。现在回头看，最大的收获不是那几行代码，而是形成了固定的问题拆解链路：先暴力估算复杂度，再想状态定义，接着推转移，最后压空间。这条链路，我后来用到所有DP题目里，极少再出现“拿到题不知道从哪下手”的窘境。
如果你也正在刷力扣hot100，我的建议是别贪多，碰到最小路径和这样的题目，值得花整块时间把它从头到尾吃干榨净。一次把二维、滚动数组、原地修改、打印路径四个方案都写一遍，比刷十道同类但浅尝辄止的题有效得多。
