先从“数路径”这个经典问题说起很多刚开始接触算法的同学遇到的第一个真正有“动态规划味”的题目多半就是n*m方格前进问题。题目本身很短一个n行m列的网格从左上角出发每一步只能向右或者向下走问走到右下角一共有多少种不同的路径。这道题在LeetCode上就是编号62的那道“不同路径”也是无数算法面试和机试的常客。别看它题干简单它其实同时踩中了动态规划的三个最核心的环节如何定义状态、如何推导状态转移方程、如何处理边界条件。把这题彻底吃透后面再碰到什么带障碍物的版本、最小路径和的版本、甚至编辑距离这种看起来完全不相干的题目你都会发现它们底层是同一套思考方式。这篇文章我就从一个老开发的角度把这道题从建模、推导、代码实现到各种变体和坑点全部过一遍希望能帮你把动态规划的基础扎牢。1. 问题建模与动态规划的解题视角1.1 先别急着写代码把问题翻译成数学语言我见过很多同学拿到这种题第一反应就是打开编辑器准备套模板这个习惯其实不太好。动态规划题最重要的不是代码本身而是动手前的“建模”——也就是把题目描述翻译成可以用状态和转移来表达的数学结构。回到这道题本身。我们先定坐标网格有n行m列左上角记为(0,0)右下角记为(n-1,m-1)。每一步只能向右或向下意味着从坐标(i,j)出发可以走到(i,j1)或者(i1,j)。反过来看如果要到达(i,j)那上一步只可能来自(i-1,j)从上面走下来或者(i,j-1)从左边走过来。这个“反过来看”的视角非常关键。它意味着当前格子的路径数量只取决于它的上方格子和左方格子与更远的格子无关。用动态规划的语言来说就是这个问题满足“无后效性”一旦过去的状态确定后面的决策不会再影响已经计算出的结果。把一个复杂问题拆解成若干个互相独立、可以递推的子问题这恰恰就是动态规划的立足点。另外这里还要提醒一个“方格”和“格子”的差异问题。有些题目说的是“n x m的网格”grid这就是有n*m个格子我们直接以上述坐标就行。但有些题目会用“n x m的方格阵”这种表述此时真正的顶点数量是(n1) x (m1)对应路径的步数也需要调整。题目如果没说明白最好先画个3x3的草图确认一下避免边界条件从一开始就是错的。我在实际面试中见过不少候选人代码思路没问题就是折在这个措辞细节上。1.2 为什么这题天然适合用动态规划而不是暴力搜索新手最容易想到的解法其实是DFS或回溯也就是沿着路径一条一条去试。对于n*m的网格总步数是固定的(n-1)(m-1)每一步有两个方向选择粗略估计就是2的(nm-2)次方种分支。哪怕n和m都只有15这个数字也已经到了千万级别完全没法接受。为什么递归这么慢因为大量的子问题被重复计算了。比如到达(2,2)这个格子可以先到(2,1)再到(2,2)也可以先到(1,2)再到(2,2)。而计算(2,1)和(1,2)的时候又都会去计算它们的上方和左方格子这意味着(1,1)会被重复计算很多次。子问题的重复度越高递归的效率就越低。动态规划的思路就是拿一张表把已经算过的结果存起来下次需要的时候直接查表不再重复计算。如果用“记忆化递归”的角度来看就是把DFS的结果缓存起来如果直接用“自底向上”的写法就是从小到大地把整张表填出来。两种方式本质一样核心都是“以前算过的不再算第二遍”这就是以空间换时间的典型体现。我把几种思路的复杂度做一个对比大家感受会更直观实现方式时间复杂度空间复杂度适用场景纯DFS递归O(2^(nm))O(nm)只适合极小的n,m记忆化递归O(n*m)O(n*m)思路直观适合推导二维动态规划O(n*m)O(n*m)通用性最强写起来最稳一维滚动数组O(n*m)O(m)空间受限时使用组合数学公式O(1)O(1)仅限纯计数且无特殊条件1.3 状态定义和转移方程的直观理解动态规划的一切都建立在状态定义上。对这道题我们定义dp[i][j] 表示从(0,0)出发到达格子(i,j)的所有不同路径数量。为什么这样定义因为路径数量是一个累加的概念唯一的入口是起点后续每一步都只能依赖上一步的位置所以我们把“到达某个格子的路径数”作为状态变量再合适不过。接下来推导转移方程。既然到达(i,j)的最后一步只可能从上方(i-1,j)或左方(i,j-1)过来那么能走到上方格子的所有路径再加一条向下走的边就都能走到当前格子同理能走到左方格子的所有路径再加一条向右走的边也都能走到当前格子。所以dp[i][j] dp[i-1][j] dp[i][j-1]这个转移方程简单到让人觉得“这也能算动态规划”但它恰恰是很多复杂DP的雏形。后面所有变体包括带障碍物、带权值本质上都是在这个方程上做文章。边界条件是第一行的格子只能从左往右走所以dp[0][j] 1第一列的格子只能从上往下走所以dp[i][0] 1。这个边界是从物理意义上自然得到的你不可能从“上方”走到第一行也不可能从“左方”走到第一列那就只有一条路可走。2. 核心细节与代码实现2.1 初始化与边界条件的三种常见写法代码本身很短但初始化写法的选择会影响代码的通用性。我先给出最标准、也最不容易出错的写法def unique_paths(n: int, m: int) - int: # dp[i][j] 表示从 (0,0) 到 (i,j) 的路径数 dp [[0] * m for _ in range(n)] # 第一列只能一直向下走只有 1 种走法 for i in range(n): dp[i][0] 1 # 第一行只能一直向右走只有 1 种走法 for j in range(m): dp[0][j] 1 # 从第二行第二列开始递推 for i in range(1, n): for j in range(1, m): dp[i][j] dp[i - 1][j] dp[i][j - 1] return dp[n - 1][m - 1]这段代码的逻辑非常清晰先处理边界再做主递推。你会发现所有动态规划题几乎都是这个套路先看“初始的已知状态”再写“怎么由已知推导未知”。还有人会图省事写成下面这样dp [[1] * m for _ in range(n)] for i in range(1, n): for j in range(1, m): dp[i][j] dp[i-1][j] dp[i][j-1]这个写法能不能过能过。因为第一行第一列恰好全部是1刚好符合路径数计数的边界条件递推公式会自动把整个表格填对。这种写法在纯路径计数里没有毛病但我非常不推荐你养成这种习惯。一旦题目变成“带障碍物”或者“最小路径和”这种偷懒初始化就是第一个翻车的点。我后面会专门讲这个坑。还有第三种写法把dp当一维滚动数组来用。它的本质是优化不是初始化我放在下一小节一起讲。2.2 空间优化从二维数组到一维数组的推导过程面试官看到你用二维数组把这道题写对了八成会追问一句“能不能优化一下空间复杂度”这时候你需要对滚动数组有清晰的理解。观察转移方程dp[i][j] dp[i-1][j] dp[i][j-1]。它只依赖当前行的左边一个元素以及上一行的同一列元素。换句话说我们从头到尾其实不需要保存整个二维表格只需要保存“上一次迭代的那一行”然后在它上面原地更新即可。具体做法是用一个长度为m的一维数组dp初始化时让dp[j]等于第一行的值也就是全1。然后在每一行迭代中从左到右更新dp[j]def unique_paths_optimized(n: int, m: int) - int: dp [1] * m # 第一行所有格子只有 1 种走法 for i in range(1, n): for j in range(1, m): dp[j] dp[j] dp[j - 1] return dp[m - 1]这段代码第一次看会有点绕因为dp[j]同时出现在等式左右两边。它的含义是这样的当外层循环还没有进入第i行时dp[j]保存的是上一行第i-1行第j列的结果进入第i行后我们按j从小到大的顺序更新当计算到j时dp[j-1]已经被更新成了当前行第j-1列的结果而dp[j]仍然是上一行第j列的结果。于是等式右边恰好就是dp[i-1][j] dp[i][j-1]赋值后dp[j]就升级成了dp[i][j]。这就是滚动数组的精髓用“同一行空间”反复覆盖上一行数据把空间复杂度从O(n*m)降到了O(m)。我可以手动摊开一个3行3列的例子验证一下。初始dp[1,1,1]进入第2行j1时dp[1]112j2时dp[2]213进入第3行j1时dp[1]213j2时dp[2]336。最终dp[2]6而3x3网格的全部路径数确实是6。如果还不放心可以拿n4,m5再推一遍结果会和二维DP完全一致。还有一个经常被问到的细节为什么j要从1开始而不是从0开始因为dp[0]在第一列永远只有1种走法不需要更新如果从0开始更新反而会把第一列的值算错。2.3 从计数到最优最小路径和问题的改造动态规划不只是用来数路径数量的它更大的价值在于求解“满足某个最优目标”的路径。比如每个格子里有一个数字表示经过这个格子需要付出的代价问从左上角到右下角路径上所有格子代价之和的最小值是多少。这就是经典的“最小路径和”问题。如果说路径计数是把来源路径数量相加那么最小路径和就是把来源路径代价取最小值再加上当前格子的代价dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]这个转移方程和路径计数的关系可以用一句话概括从“累加可能性”变成“比较优劣”。边界条件也跟着变化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]。这里就能看出前面说的“初始化别偷懒”有多重要了。最小路径和的边界值不是固定不变的1而是依赖前一个格子累加出来的结果。如果你还用“把边界全初始化成1”的那种写法结果必错。写最小路径和时可以用一个技巧把dp数组初始化为一个很大的数比如float(inf)然后只设定dp[0][0]grid[0][0]在循环里用min操作逐步推。这种写法虽然多算些边界格子但代码统一思维负担也小适合在比赛或面试时快速保正确。3. 变体与进阶扩展3.1 带障碍物的路径计数与初始化陷阱地图上不是所有格子都能走这太正常了。如果某些格子有障碍物题目就升级成了LeetCode-63“不同路径II”。做法其实就是在原版基础上加一个判断如果当前的格子是障碍那dp[i][j]直接等于0否则才套用原来的递推公式。但这个变体最阴险的地方在初始化。很多同学沿用“第一行第一列全是1”的惯性结果遇到第一行某个位置有障碍时障碍右侧的所有格子其实都不可达路径数应该是0而不是1。比如第一行的第3个格子是障碍那第4个格子、第5个格子都到不了因为向右走会被障碍挡住。我推荐一个不太容易写错的写法把所有dp先初始化为0再直接用三重条件判断来递推而不是手动处理边界。代码如下def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) - int: n len(obstacle_grid) m len(obstacle_grid[0]) # 起点就是障碍直接返回 0 if obstacle_grid[0][0] 1: return 0 dp [[0] * m for _ in range(n)] dp[0][0] 1 for i in range(n): for j in range(m): if obstacle_grid[i][j] 1: dp[i][j] 0 continue if i 0: dp[i][j] dp[i - 1][j] if j 0: dp[i][j] dp[i][j - 1] return dp[n - 1][m - 1]这段代码里dp[0][0]先设为1然后从(0,0)开始遍历。当遇到障碍时把dp置0并跳过非障碍时把上、左两个方向的路径加起来。注意循环是从i0,j0开始的但(0,0)这个格子已经预先设好了初始值1而且此时i0和j0都不满足不会重复累加。这个写法的好处是无论障碍物出现在第一行、第一列还是中间位置逻辑都是统一的不会遗漏边界情况。同理终点如果是障碍最终dp[n-1][m-1]会是0符合直觉。这道题还有一个更保险的优化把obstacle_grid本身当作dp表格来更新从而省掉额外空间。不过原地修改会破坏输入数据面试时可以主动提一句“如果允许修改输入可以原地处理省空间”这会是个不错的加分项。3.2 如何把路径方案打印出来有些题目不满足于让你算数量还会让你输出一条具体路径甚至要求在满足某种条件下输出字典序最小的路径。这时候动态规划仍可以派上用场。先说输出“任意一条路径”。你可以在完成DP表格后从终点开始反推站在(i,j)如果dp[i][j]等于dp[i-1][j]即这个格子是从上方过来的就说明走法里有向下的成分如果等于dp[i][j-1]说明是从左边来的如果两者都成立说明两边都能到挑一条就行。按这个方式一路回溯到起点再把路径反转就是一条合法路径。如果是“字典序最小的路径”思路也类似但方向要反过来从起点开始每一步优先尝试向右走如果dp状态显示右边那格确实可以到达就走右边否则走下方。因为“向右”在字典序里通常比“向下”更“小”这样做贪心选择就能得到字典序最小的路径。需要提醒一下如果你要求输出“所有路径”而不只是数量动态规划就英雄无用武之地了。因为路径总量本身就可能是指数级别的比如在3x3的网格里就有6条路径到10x10时已经是几万条全量输出无论用什么方法都跑不掉这个数量级。这种场景应该用DFS/回溯去枚举动态规划反而不合适。明白“什么场景用什么工具”才是经验值增长的标志。3.3 从棋盘到拓扑排序动态规划的思维迁移很多人觉得动态规划就是刷题用的和真实工作没什么关系。其实完全不是这样。仔细观察一下你会发现n*m方格前进问题里网格本身就是一张“有向无环图”每个格子是一个节点只能向右或向下走意味着所有边的方向都是一致的因此图中不可能出现环。只要是有向无环图上的路径计数或最短路问题都可以用同一个DP框架来解决只不过遍历顺序要从网格的“按行按列”推广成“按拓扑序”。举个例子项目管理里的关键路径分析本质上就是在一个有向无环图上做DP每个任务是一个节点任务之间的依赖关系是边每个节点有自己的耗时求整个项目从开始到结束最早要多久。我当年第一次意识到运维平台的依赖构建顺序可以用这套思路来优化时确实是眼前一亮。所以学这道题真正有价值的不只是一个答案而是一种“建模能力”把现实问题抽象成状态和转移再用递推的方式求解。你以后遇到任何“有先后顺序”“又需要最优方案”的问题都可以先想想能不能套上这套框架。4. 常见问题与避坑技巧4.1 边界条件初始化总翻车怎么办我做算法面试官这些年看过太多次候选人栽在初始化上。很多人转移方程写得飞快一到边界就崩盘。这里帮你把最常见的翻车场景整理成一张速查表翻车现象产生原因解决方案结果比预期大很多边界批量初始化成1时没考虑障碍物带障碍时用三重条件判断不要批量初始化结果比预期小循环起点或坐标方向搞反用i表示行、j表示列先画3x2草图验证数组越界或负数索引n和m参数混淆统一约定n为行数、m为列数写注释说明大n,m下数据溢出int类型存不下天文数字每步加法后取模或用大整数方案空间超限n*m太大导致二维数组过大改一维滚动数组或直接用组合数学公式关于n和m谁在前谁在后的问题我多说一句。很多题目的原文是“m x n grid”但各题解用的变量名五花八门有时候中文题解又顺手把行数叫成n导致两套代码很难对照。我自己的习惯是不管题目怎么说一律把行数叫n列数叫m并且在代码顶部写清楚“n行数m列数”。画图验证时也统一用行列的视角去看避免在循环里把i和j颠倒。4.2 大数溢出的应对与模运算纯路径数量增长有多夸张10x10的网格路径数是C(18,9)48620看着还好到25x25的网格结果已经是C(48,24)大约6e13到50x50结果妥妥超过1e29早就超出了64位整数能表示的范围。所以在一些竞赛和机试里题目往往会要求“对10^97取模”输出。取模的写法很简单每一次状态转移做加法时就取一次模不要等最后统一取模否则中间结果早溢出了dp[i][j] (dp[i-1][j] dp[i][j-1]) % MOD如果你用的是Python整型不会溢出有时候容易忽略这个问题但在Java和C里int类型在n和m稍大一点就会爆。养成每步取模的习惯以后做更多DP题都会受益。这里还要提一个组合数学方案的取模问题。无障碍情况下答案就是组合数C(nm-2, n-1)。如果要求取模那么计算组合数时的除法不能直接做必须使用模逆元。假如你正在打比赛对数论不太熟最稳妥的方案就是老老实实写DP。取模DP的做法没有数学门槛代码又短我用它处理过很多机试题目从未失手。4.3 面试现场该怎么讲这道题如果面试官把这道题丢给你那多半不是只想听到一个正确答案而是想观察你的分析过程。我建议按下面这个顺序来表达第一步确认模型。复述一遍“n行m列只能向右和向下求路径数”顺便和面试官对齐坐标约定这能展示你对细节的敏感。第二步讲状态定义。明确说出dp[i][j]的含义是“从起点到(i,j)的路径数量”。第三步讲状态转移。解释为什么dp[i][j]等于dp[i-1][j]加上dp[i][j-1]因为最后一步要么从上方来要么从左方来。第四步讲边界条件。说明第一行和第一列为什么是1或者在你的写法里为什么能被统一处理。第五步讲复杂度并主动提优化。先给出时间O(nm)、空间O(nm)然后接着说“空间上其实可以压缩到O(m)”并现场改写。第六步如果还有余力顺口提一句“如果没有障碍这个答案也可以用组合数学直接算但带障碍场景还是DP更通用”。这就把深度展示出来了。这一套讲下来面试官基本能确认你对动态规划是有真实理解的而不只是背过模板。很多人能写对但讲不明白其实吃亏在平时解题时没养成“先讲思路再写代码”的习惯。4.4 我把实际做题的固定套路再总结一下这里更像是写给正在刷题的朋友们的一点实战心得。我自己这几年处理DP题的习惯是四步走画图、定义、转移、回看。画图永远是第一步。3x3也好3x2也好把网格画出来把dp值一步一步填进去。你很快就能从具体数字中找出规律而不是空想公式。定义状态时一定要把“dp[i][j]到底存的是什么”用一句话写清楚。比如“从起点到(i,j)的路径数”和“从(i,j)到终点的路径数”是完全不同的两个定义写的代码也不一样。同一个题两个定义都能做对但在一道题里换定义代码就会很别扭这个我自己也踩过。转移方程写出来以后对着小图手算一遍确保第一行第一列的值符合边界。很多bug在纸上就能发现根本不用等运行。最后是“回看”。每次写完一道DP题我都会问问自己这个状态能不能降维能不能滚动如果题目加个限制条件我的框架还成立吗这种回看能帮你把一个题吃透成十种解法远比草草刷十道题更有价值。再说一个实战中非常实用的小技巧如果题目要求输出路径我倾向于在DP表算完之后再单独做一次“反推遍历”而不是在DP循环里顺便记录方向。这样代码职责清晰也方便调试。之前在给项目做数据血缘分析工具时我就是在DAG上先做DP算关键路径再反推还原出完整链路和棋盘路径的思路完全一致。动态规划真的不只是面试玩具。