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)导致同一个子问题被算了不知道多少遍。m20、n20 的时候这个递归的调用次数是指数级的跑起来让人绝望。我为什么非要提这个笨办法因为动态规划的本质就是用空间换时间把递归里的重复计算缓存起来。你得先看见重复在哪里才能理解 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次向右总共mn-2步。路径的区别只在于这 mn-2 步中哪些步选择向下。所以方案数就是组合数C(mn-2, m-1)也就是从 mn-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) 更快但有个致命问题组合数增长极快。m100、n100 的时候组合数的数量级已经超出了一个普通的 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 三份代码的对比二维、一维、原地修改第一版是标准的二维 DPdef 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 高频错误速查表我整理了一张表把这两道题最常见的报错原因和排查方向列出来都是我在实际刷题和帮人改代码时反复见过的错误现象根本原因排查方向结果比预期小很多初始化第一行第一列错误比如最小路径和里把第一行初始化成了同一值单独打印第一行和第一列的 dp 值手动验证累加报 IndexError遍历范围写错比如直接用 m 遍历列或者range(m)和range(n)搞混写出网格的行列数确认dp[i-1][j]中 i 不为 0Python 中修改一个格子整列都变用[[0] * n] * m创建二维数组子列表是同一个引用改用列表推导式[[0] * n for _ in range(m)]答案正确但超时用了暴力递归或记忆化搜索没有剪枝改成自底向上填表复杂度降到 O(m*n)大矩阵下结果为负数组合数学解法遇到整数溢出改用动态规划或在题目要求下取模滚动数组结果混乱内层循环遍历方向错误从左往右扫并验证 dp[j-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 里现场分析出一道从没见过的变式题。矩阵里的动态规划千变万化但核心永远是把大问题拆成只差一步的小问题找到那个递推关系一切就都顺了。