不同路径与最小路径和：动态规划网格题的同源解法与初始化陷阱

1. 先把两道题放进同一个框架里看

1.1 核心需求：数方案和求最优值，共用同一张状态表

动态规划里关于 m*n 矩阵的题目，最常被刷题群拿来当模板的就是这两道：不同路径（从左上角走到右下角一共有多少种走法）和最小路径和（每个格子有代价，从左上角走到右下角怎么走代价最小）。标题把这两题放在一起，其实很有道理——你仔细对比就会发现，它们的状态定义几乎一模一样，都是dp[i][j]表示"从起点走到格子 (i, j) 的某个答案"，转移的时候都只看左边和上边两个邻居，区别只是一个是加法一个是取最小值。

这个共同点不是巧合。这两道题本质上都是"二维网格上的递推"，满足动态规划的两大前提：有重叠子问题，有最优子结构。你在 (i, j) 这个位置的答案，只依赖它左边和上边的结果，不存在回头路，也不存在跨格子的跳跃，所以只需要一个方向地推下去就能得到最终答案。

很多新手容易犯的毛病是孤立地记题解：背下不同路径的代码，背下最小路径和的代码，结果遇到带障碍物的版本又懵了。我更建议你把这两道题当作同一个模型的两个实例来学，先搞清楚"为什么这个状态转移是对的"，再去背代码就不会那么痛苦。

1.2 为什么这两题被当成入门必修

我先说结论：它们是动态规划里最典型的"网格型 DP"代表，难度适中，但延展性极强。互联网公司笔试里，这类题的变体层出不穷——带障碍物、带权重、求最小代价、求最大价值、限定步数、允许走斜线等等，但底层的表格填充逻辑基本不变。

适合谁来读呢？我建议三类人认真看：第一类是刚开始学动态规划、被"状态转移方程"这个概念劝退过的初学者；第二类是刷题刷到中等题卡壳、想把模板题吃透的求职者；第三类是面试官喜欢从这两题切入考察候选人基本功的从业者——说实话，这两题虽然简单，但能把边界条件、空间优化、初始化细节讲得滴水不漏的人，真的不多。

2. 从暴力递归到动态规划：完整推演一遍

2.1 暴力递归：先把最笨的方案写对

很多人上来就写二维循环填表，但我觉得理解动态规划最稳的路径是先从暴力递归开始。以"不同路径"为例，从 (i, j) 出发到右下角，每次只能向右或向下走一步，那么递归函数可以写成：到达 (i, j) 的方案数，等于到达 (i-1, j) 的方案数加上到达 (i, j-1) 的方案数。写成代码就是这样：

def unique_paths_recursive(m: int, n: int) -> int: def dfs(i: int, j: int) -> int: if i == 0 or j == 0: return 1 return dfs(i - 1, j) + dfs(i, j - 1) return dfs(m - 1, n - 1)

这个版本有一个很直观的问题：重复计算。你算dfs(2, 2)的时候会去算dfs(1, 2)和dfs(2, 1)，而这两个又会各自去算dfs(1, 1)，导致同一个子问题被算了不知道多少遍。m=20、n=20 的时候，这个递归的调用次数是指数级的，跑起来让人绝望。

我为什么非要提这个笨办法？因为动态规划的本质，就是"用空间换时间，把递归里的重复计算缓存起来"。你得先看见重复在哪里，才能理解 dp 表存在的意义。

2.2 记忆化搜索：一张备忘录消掉重复计算

给递归加上一个缓存字典，让每个 (i, j) 只算一次，这就是记忆化搜索。它和自底向上的动态规划在状态定义和转移逻辑上完全等价，只是方向是从上往下"搜"的：

def unique_paths_memo(m: int, n: int) -> int: memo = {} def dfs(i: int, j: int) -> int: if i == 0 or j == 0: return 1 if (i, j) in memo: return memo[(i, j)] memo[(i, j)] = dfs(i - 1, j) + dfs(i, j - 1) return memo[(i, j)] return dfs(m - 1, n - 1)

时间复杂度从指数级降到了 O(m*n)，每个格子最多算一次。这里的 memo 就是一张二维表的"懒加载"版本。理解了这一步，你再去看自底向上的填表代码，会豁然开朗：dp 表其实就是 memo，只不过我们提前规划好了计算顺序，从最小的子问题开始填，一层层推到目标答案。

2.3 自底向上填表：最终形态怎么来的

自底向上就是顺着网格从左到右、从上到下地填。因为 (i, j) 只依赖 (i-1, j) 和 (i, j-1)，只要保证计算 dp[i][j] 的时候左边和上边已经算好了，按行遍历就天然满足这个依赖顺序。这也是动态规划最常见的代码形态：

def unique_paths(m: int, n: int) -> int: dp = [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m - 1][n - 1]

我把第一行和第一列全部初始化为 1，这样内层循环就可以从 (1, 1) 开始跑，省去特判。这个初始化逻辑对不对，后面我会专门展开讲，因为它是很多人写错的重灾区。

3. 不同路径：数方案数的关键细节

3.1 状态定义与转移方程推导

"不同路径"的题目表述通常是这样的：一个机器人位于 m x n 网格的左上角，每次只能向下或者向右移动一步，请问到达右下角总共有多少条不同的路径？

状态定义我习惯写成：dp[i][j]表示从起点 (0, 0) 走到格子 (i, j) 的路径条数。转移方程是dp[i][j] = dp[i-1][j] + dp[i][j-1]。

这一步推导逻辑要讲清楚：要走到 (i, j)，最后一步只可能来自上方 (i-1, j) 或左方 (i, j-1)。而"从起点到上方格子"的路径条数是dp[i-1][j]，"从起点到左方格子"的路径条数是dp[i][j-1]，这两类路径不会重叠，因为最后一步的方向不同，所以总数直接相加。

这里有个容易被忽略的点：为什么不能是乘法？你可能会想，到达上方的每种路径都要搭配到达左方的每种路径吗？不是的，因为每个具体路径只对应一个最后一步的方向，你不能既从上方来又从左方来。加法是"二者选其一"的计数，乘法才是"搭配组合"的计数。想通这一点，后面遇到"先走几步再走几步"的组合类题目就不容易错。

3.2 初始化的一行代码，很多人写错

初始化是这道题最容易翻车的地方。第一行的每个格子，只能一路向右走来，所以路径数都是 1；第一列的每个格子，只能一路向下走来，路径数也都是 1。所以dp[0][j] = 1、dp[i][0] = 1天然成立。

有些写法是把整个表先填 0，然后单独给第一行第一列赋 1，再跑双重循环。这也没问题，但更简洁的做法是像我上面那样，初始化的时候就构造[[1] * n for _ in range(m)]，把整个表先填成 1，这样第一行第一列天然正确，内层循环直接从 (1, 1) 开始。

这里有一个新手常踩的坑：有人把初始化写成[[1] * n] * m，这在 Python 里会出大问题。外层用乘法复制的是同一个列表对象的引用，你改dp[0][0]，会发现整列都跟着变。正确的写法必须是列表推导式[[1] * n for _ in range(m)]，每个子列表都是独立对象。这种引用共享问题在面试手写代码时特别容易暴露，我见过不止一个候选人在白板上栽在这里。

3.3 组合数学解法与大数溢出问题

不同路径其实还有一层数学本质：从左上角到右下角，一共要走m-1次向下、n-1次向右，总共m+n-2步。路径的区别只在于这 m+n-2 步中，哪些步选择向下。所以方案数就是组合数C(m+n-2, m-1)，也就是从 m+n-2 个位置里选 m-1 个位置作为向下走的步。代码可以写成：

import math def unique_paths_math(m: int, n: int) -> int: return math.comb(m + n - 2, min(m - 1, n - 1))

用min(m-1, n-1)是为了选较小的那个数来计算，减少运算量。这个解法的时间复杂度是 O(min(m, n))，比 DP 的 O(m*n) 更快，但有个致命问题：组合数增长极快。m=100、n=100 的时候，组合数的数量级已经超出了一个普通的 64 位整数能表示的范围。很多在线评测系统里，这道题给的返回值是 int，但如果你在本地测试大矩阵，就会看到整数溢出变成负数。

这时候你得想清楚平台约束：如果题目不要求取模，结果保证在 int 范围内，那么组合数学解法非常优雅；如果要求取模或者矩阵特别大，老老实实写动态规划反而没有溢出烦恼，因为每一步加法都只保留最终计数。另外一个细节是，如果 m 和 n 有一个是 1，组合数学公式依然成立，因为C(n-1, 0) = 1，正好只有一条直线路径。

4. 最小路径和：求最优值的边界陷阱

4.1 状态转移与第一行第一列的特殊处理

"最小路径和"的题目表述是这样的：给定一个包含非负整数的 m x n 网格 grid，每次只能向下或者向右移动一步，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

状态定义依然是dp[i][j]表示从左上角走到 (i, j) 的最小路径和。转移方程是dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。因为你最后一步要么从上面下来，要么从左边过来，选择代价更小的那条路，再加上当前格子的值，就是到当前格子的最小代价。

但这里和"不同路径"有一个本质区别：第一行和第一列不能统一赋 1 了，因为每个格子上的数字不同，路径和必须累加。第一行只能一路向右走，所以dp[0][j] = dp[0][j-1] + grid[0][j]；第一列只能一路向下走，所以dp[i][0] = dp[i-1][0] + grid[i][0]。起点dp[0][0]就是grid[0][0]本身。

我总结一个规律：凡是"求方案数"的题，第一行第一列通常初始化成 1 或 0 这种定量；凡是"求路径和/代价"的题，第一行第一列必须逐格累加原始数据。很多人在不同路径里习惯了初始化成 1，做最小路径和的时候想当然地也填 1，结果答案完全不对。一定要先搞清楚每个状态的含义，再决定初始化的值。

4.2 三份代码的对比：二维、一维、原地修改

第一版是标准的二维 DP：

def min_path_sum(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]

第二版是滚动数组优化，只用一行变量：

def min_path_sum_1d(grid): 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[n - 1]

第三版是原地修改原矩阵，不额外开数组：

def min_path_sum_inplace(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 if 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]

三份代码的输出结果完全一样，区别在空间复杂度：第一版 O(m*n)，第二版 O(n)，第三版 O(1)。做题的时候如果题目允许修改原数组，我建议直接用第三版，又省空间又不用处理额外的初始化逻辑，面试时还能体现你对空间的敏感度。但如果你是在封装给别的模块调用，原数组可能还有别的用途，那就别动它，用第一版最稳妥。

4.3 空间压缩的原理与覆盖顺序讲究

滚动数组为什么能成立？关键在于我们按行遍历的时候，dp[j]这个位置的上一轮值，其实就是上一行同列的结果；而更新时等号右边的dp[j-1]，在从左往右遍历的当下已经被更新成了当前行左列的结果。也就是说，dp[j]更新前代表dp[i-1][j]，dp[j-1]更新后代表dp[i][j-1]，两者正好是转移方程需要的两个值。这就是"边遍历边覆盖"的原理。

这里的覆盖顺序有个必须注意的点：内层循环一定是从左往右，不能从右往左。如果从右往左扫，dp[j-1]还没有被当前行更新，它仍然是上一行的旧值，那你拿到的就是dp[i-1][j-1]而不是dp[i][j-1]，结果就错了。这个坑在"01 背包"里恰恰相反——背包从右往左扫是为了避免重复拿同一件物品，很多从背包题转过来的人容易把顺序记混。我的建议是每次写滚动数组都实际推演一行，别死记"从左还是从右"。

5. 常见错误与调试排查实录

5.1 高频错误速查表

我整理了一张表，把这两道题最常见的报错原因和排查方向列出来，都是我在实际刷题和帮人改代码时反复见过的：

我特别想强调 Python 的引用共享问题。不只是上面说的二维数组乘法，使用copy模块的deepcopy也会带来不必要的开销。写算法题时，最干净的做法就是列表推导式。如果你在调试时发现打印出来的 dp 表对称得诡异，或者改一个格子其它格子跟着变，基本就是这个原因。

5.2 一套可复现的调试方法

遇到 DP 题结果不对，我推荐一个固定的调试套路：先找一个非常小的用例，比如 2x2 或 3x3 的矩阵，手工在纸上把每一步 dp 值算出来，然后让程序打印每一步的 dp 表，逐格对比。

以最小路径和为例，网格[[1, 3, 1], [1, 5, 1], [4, 2, 1]]，正确答案是 7。我调试时会在循环里加一行打印：

for i in range(m): for j in range(n): if i == 0 and j == 0: continue if 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]) print(grid[i])

你会看到第一行处理后变成[1, 4, 5]，第一列处理后第二行变成[2, 5, 1]，继续处理最后得到整个矩阵。手动推演一遍后，你会发现错误往往出在"边界格子被错误地用了min而不是累加"上。这类问题肉眼很难看出来，但打印出中间过程就一目了然。

另一个技巧是加断言。如果你确定最终结果应该落在某个范围，比如最小路径和一定不会小于第一行第一列的值，也不会大于所有格子值之和，可以临时加assert帮助快速定位。虽然刷题时不一定需要，但在本地调试阶段它真的能救命。

5.3 两道变式题：障碍物版本与三角版本

搞定了两道基础题，我建议趁热打铁练两道同源变式。

第一道是"不同路径 II"，网格中有些格子有障碍物，机器人不能进入。状态转移时，如果当前格子是障碍物，dp[i][j]直接为 0；否则仍然等于上边和左边之和。初始化也要跟着改：第一行第一列一旦遇到障碍物，后面所有格子都到不了，必须是 0。

def unique_paths_with_obstacles(obstacle_grid): m, n = len(obstacle_grid), len(obstacle_grid[0]) dp = [[0] * n for _ in range(m)] if obstacle_grid[0][0] == 1: return 0 dp[0][0] = 1 for j in range(1, n): dp[0][j] = 0 if obstacle_grid[0][j] == 1 else dp[0][j - 1] for i in range(1, m): dp[i][0] = 0 if obstacle_grid[i][0] == 1 else dp[i - 1][0] for j in range(1, n): if obstacle_grid[i][j] == 1: dp[i][j] = 0 else: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m - 1][n - 1]

第二道是"三角形最小路径和"，三角形类似一个下三角矩阵，从顶点到底部的最小路径和。它的状态转移变成dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])，因为上一行只有两个格子可能到达当前位置。这类变式的核心难点就在于边界格子的处理，比如每行的第一个格子只能从上一行的第一个格子来，每行的最后一个格子只能从上一行的倒数第二个来。我建议你把三角形补齐成一个矩形，多出来的格子填一个大数，这样就能复用矩形的通用逻辑，避免一堆分支判断。

这两道变式题做完，你会发现一个规律：所有的网格型 DP 题目，核心就是"状态定义 + 转移方程 + 边界处理"三件套。题目的包装再多，只要这三件套想清楚，代码基本是一次写对的。

6. 写在最后：几个让我受益的习惯

这两道题我前前后后写了不下五遍，每次重写都有新体会。最后分享几个我自己的习惯，希望能帮你少走弯路。

第一个习惯是先写暴力递归再优化。哪怕面试的时候时间紧张，我也会先在草稿纸上写出递归的思路，再转化成 DP。这个动作看起来多花了半分钟，但它能帮你验证状态转移的正确性。递归版本如果逻辑错了，DP 版本一定也是错的，而且错得更难发现。

第二个习惯是每道 DP 题都追问自己三个问题：状态是什么？转移从哪里来？边界在哪里？这三个问题如果都能准确回答，不用看代码，你就能判断解法对不对。我自己面试别人时也常问这三连，能答得干脆利落的候选人，代码水平一般都不差。

第三个习惯是关于空间优化的。新手阶段我建议先把二维版本写对，再去优化成一维或原地修改。直接跳步写滚动数组，一旦出错，你很难判断是算法本身错了还是空间压缩过程引入的 bug。顺序是：先正确，再高效。这也是为什么我这篇博文把二维版本和一维版本都完整写出来对比。

最后再提一句：如果你是在准备面试，这两道题的"标准解法"要熟练到不用思考就能默写，但更重要的是能把转移方程的推导过程讲清楚。面试官最想看的不是你会背题，而是你能在 chat 里现场分析出一道从没见过的变式题。矩阵里的动态规划千变万化，但核心永远是把大问题拆成"只差一步"的小问题，找到那个递推关系，一切就都顺了。