如果你在网上搜“n*m方格前进问题”大概率会刷到满屏的状态转移方程和代码模板。但真正奇怪的是评论区永远有一批人在问为什么我照着写了还是错为什么网格里加几个障碍物我就不会了为什么别人用一维数组能跑对我换成滚动数组答案就变了这篇文章不打算把经典动态规划法标准答案再抄一遍而是把这道入门题彻底拆开——从“为什么用DP、不用组合数”开始到状态定义、转移方程、空间优化再到障碍物、路径回溯、带权重路径这些高频变体最后聊几个我在实际做题和面试中反复踩过的坑。无论你是刚学DP的小白还是准备机试的刷题党按这个思路走一遍会发现这类“方格前进”的题其实就是同一个套路。1. 这道题凭什么能成为动态规划的入门必刷题1.1 先把问题说清楚再谈第一反应题目描述很简短在一个 n 行 m 列的方格网格中从左上角出发每次只能向右或向下移动一格问到达右下角一共有多少种不同的走法。很多人的第一反应是高中数学里的组合数整个旅程一共要走 (n-1)(m-1) nm-2 步其中选择 n-1 步向下走剩下的自然就是向右所以答案是 C(nm-2, n-1)。这种解法遇到纯知识竞赛恰好够用比如 n3、m4 时答案就是 C(5,2)10。但问题是这个公式有两个隐性的前提一是网格里不能有任何障碍物二是每个格子都能畅通无阻地经过。只要题目稍微加一个条件说某些格子不能走组合数公式马上就抓瞎了。你可能说“那就用容斥原理绕开障碍”可一旦障碍物变多、位置变复杂容斥的公式会膨胀到你根本不想看。1.2 为什么“最后一步”是动态规划的关键入口动态规划处理这个问题的方式和组合数完全不同。它不去想整条路径怎么安排而是只盯着一个很朴素的问题到达某个格子 (i, j) 的最后一步是从哪里迈进来的因为限制只能向右和向下走所以到达 (i, j) 的最后一步只可能是从上方 (i-1, j) 下来或者从左方 (i, j-1) 过来。于是到达 (i, j) 的走法数量就等于到达 (i-1, j) 加上到达 (i, j-1) 的数量。这一步想明白了后面的代码只是把这句话翻译成程序而已。这个过程其实可以类比成爬楼梯走到第 k 级台阶要么从第 k-1 级迈一步要么从第 k-2 级迈两步所以方案数是 f(k)f(k-1)f(k-2)。方格前进就是一个二维版的楼梯问题只是把两个方向从“前一步、前两步”扩展成了“上方、左方”。想通了这一层DP 就不再是背模板而是一种自然的递推思维。1.3 无后效性是这类题能用DP的根本原因动态规划能成立依赖一个叫“无后效性”的性质当前格子的状态只依赖它上面和左边的格子而和之前具体走了什么路线没有任何关系。换句话说不管你是绕了三条路才到 (i-1, j)还是笔直走过来的对 (i, j) 的方案数贡献都一样。这种性质保证了我们可以从左上角开始一层层往右下角推而不用回头改已经算好的结果。方格前进问题之所以经典正是因为它把“无后效性”展现得极其直观——想明白这一点后面遇到更复杂的DP思路会清晰很多。2. 状态定义和转移方程三步拿下一个二维DP2.1 状态定义dp[i][j] 到底表示什么写DP题第一步永远是定状态状态定义错了后面全白搭。对于这个题我习惯用 0-based 索引让 dp[i][j] 表示从左上角走到坐标为 (i, j) 这一格的不同路径数其中 i 的范围是 0 到 n-1j 的范围是 0 到 m-1。左上角就是 (0,0)右下角就是 (n-1, m-1)。这里有个容易混淆的细节题目里 n 是行数m 是列数但有的 OJ 题目参数名直接写 m、n含义却反过来了。我早期做题就因为这个把 dp 数组建反过样例越界直接报错。看题的时候一定要先确认“第一个参数是行还是列”再决定 dp 的维度怎么开。如果非要用 1-based 索引让 dp[i][j] 表示走到第 i 行第 j 列的方案数思路完全一样边界处理略有差别但本质没有区别。我建议初学者统一用 0-based这样和代码里数组下标天然对齐省去很多等价变形的烦恼。2.2 转移方程最后一步从哪来因为只能向右或向下走所以 (i, j) 只能由 (i-1, j) 或 (i, j-1) 转移而来。于是转移方程就是dp[i][j] dp[i-1][j] dp[i][j-1]这句话其实就是整道题的核心。实际操作时不需要真的在代码里做“左上角往右、往下推”的操作只需要按行从左到右遍历每个格子用上面这个式子把 dp 表填满就行。为什么按行从左到右遍历是对的因为计算 dp[i][j] 需要 dp[i-1][j]上一行已经算过了和 dp[i][j-1]当前行左边刚算完所以遍历顺序从第 1 行第 1 列开始一行一行往右走保证依赖的两个值都已就绪。2.3 边界条件为什么第一行和第一列全是1按照转移方程dp[0][0] 左边和上面都不存在格子得单独处理。这里的关键认知是第一行的格子只能从左边一路向右走过来所以 dp[0][j] 全是 1第一列的格子只能从上面一路向下走过来所以 dp[i][0] 也全是 1。初始化时可以直接先把整个 dp 数组清零再给第一行和第一列赋 1。但更简洁的写法是初始化时就用循环处理for (int j 0; j m; j) dp[0][j] 1; for (int i 0; i n; i) dp[i][0] 1;然后从 i1、j1 开始双循环填表。这个方法之所以行得通是因为 (0,1) 只能从 (0,0) 向右走方案数就是 1(1,0) 只能从 (0,0) 向下走方案数也是 1。边界上根本没有第二个方向可以选所以初始化的逻辑和现实一一对应。2.4 手推一个3×4网格看看状态表怎么变理论讲多了容易飘拿一个具体的 n3、m4 的例子把 dp 表完整填一遍。初始状态先处理边界第一行dp[0][0]1dp[0][1]1dp[0][2]1dp[0][3]1第一列dp[1][0]1dp[2][0]1然后从 i1、j1 开始dp[1][1] dp[0][1] dp[1][0] 1 1 2dp[1][2] dp[0][2] dp[1][1] 1 2 3dp[1][3] dp[0][3] dp[1][2] 1 3 4dp[2][1] dp[1][1] dp[2][0] 2 1 3dp[2][2] dp[1][2] dp[2][1] 3 3 6dp[2][3] dp[1][3] dp[2][2] 4 6 10最终答案是 10和组合数公式算出来的结果一致。你可以发现dp 表其实是把组合数的累积过程一步一步“画”了出来。这个过程建议新手在纸上完整演算两遍因为很多面试官在考察动态规划时都会让你现场手推一个小例子能流畅推出来比背代码有说服力得多。3. 从递归到一维数组三种递进写法3.1 最直观的递归思路清楚但指数爆炸学DP前很多人习惯用 DFS 或者递归写这类题。递归你可以直接写成这样int dfs(int i, int j) { if (i 0 || j 0) return 1; return dfs(i - 1, j) dfs(i, j - 1); }这个写法完全符合转移方程逻辑上挑不出毛病但性能上是个灾难。因为 dfs(i,j) 会递归调用 dfs(i-1,j) 和 dfs(i,j-1)其中大量子问题是重叠的。比如 dfs(2,2) 需要算 dfs(1,2) 和 dfs(2,1)而这两者都依赖 dfs(1,1)导致 (1,1) 会被重复计算很多次。整个递归树的大小接近指数级n 和 m 一上来就卡死。你在本地 nm10 的时候可能还能跑出结果但放到 nm30 就明显感觉卡顿nm50 基本就等不到结果了。正因为存在大量重复计算我们才需要“记忆化”或者干脆自底向上迭代。3.2 记忆化DFS给递归加个缓存最简单的优化就是给递归加一个 memo 数组让每个子问题只算一次int n, m; vectorvectorint memo; int dfs(int i, int j) { if (i 0 j 0) return 1; if (i 0 || j 0) return 0; if (memo[i][j] ! -1) return memo[i][j]; return memo[i][j] dfs(i - 1, j) dfs(i, j - 1); }这种方式叫“自顶向下”的记忆化搜索时间复杂度从指数级降到 O(nm)空间复杂度也是 O(nm)。它比递归版看似只加了几行但性能天差地别。难点在于边界条件的处理。这里我把 (0,0) 单独返回 1越界返回 0可以保证所有状态都能正确推导。很多初学者容易写成 if (i 0 || j 0) return 1这种写法也能对但遇到障碍物变体时就不够通用了。3.3 经典迭代DP用双重循环填表记忆化搜索虽然好理解但实际刷题最常用的还是自底向上的迭代写法因为不需要递归函数调用栈常数更小也更容易做空间优化。二维数组版本长这样int uniquePaths(int n, int m) { vectorvectorint dp(n, vectorint(m, 0)); for (int j 0; j m; j) dp[0][j] 1; for (int i 0; i n; i) dp[i][0] 1; for (int i 1; i n; i) { for (int j 1; j m; j) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } return dp[n - 1][m - 1]; }这段代码没什么技巧就是照着转移方程填表。但你别小看它这是后面所有变体的地基。面试时如果时间紧张写这种版本最稳逻辑一目了然面试官也好跟你的思路。3.4 滚动数组/一维优化空间从O(n*m)降到O(m)二维数组能解决大部分问题但有些题对空间有严格要求或者 n、m 特别大这时候就要用滚动数组。观察转移方程会发现计算当前行 dp[i][j] 时用到的是上一行的 dp[i-1][j] 和当前行左边的 dp[i][j-1]根本不需要保留所有历史行。所以完全可以用一个长度 m 的一维数组滚动复用。int uniquePaths(int n, int m) { vectorint dp(m, 1); // 初始化为第一行的值 for (int i 1; i n; i) { for (int j 1; j m; j) { dp[j] dp[j - 1]; } } return dp[m - 1]; }这段代码的精妙之处在于dp[j] 在更新前存的是“上一行的第 j 列值”对应转移方程里的 dp[i-1][j]dp[j-1] 在内层循环里刚被更新过对应的是“当前行的第 j-1 列值”也就是 dp[i][j-1]。两者相加正好等于新的 dp[j]。这里有个致命细节内层循环必须从左往右遍历 j。如果从右往左遍历dp[j-1] 还是上一行的旧值相当于把“当前行左边”用成了“上一行左边”结果完全错误。我见过不少人背了一维数组的写法却败在遍历方向上所以这地方值得多划几笔。Python 版本换汤不换药def unique_paths(n: int, m: int) - int: dp [1] * m for i in range(1, n): for j in range(1, m): dp[j] dp[j - 1] return dp[-1]如果你对一维滚动数组一时转不过弯建议先在纸上把 3×4 的 dp 表用两行“当前行和上一行”推一遍再对照代码看很快就能理解为什么只开一个一维数组就足够。4. 从“数路径”到“找路径”三个高频变体一次讲透4.1 加障碍物状态转移多了一个“不可达”分支方格前进最经典的变体是在网格中放若干障碍物值为 1遇到障碍物的格子不能走求仍然到达右下角的路径数。这个变体几乎击碎了“直接用组合数公式”的幻想因为路径集合被局部破坏后简单的排列组合公式没法直接翻译成“绕开这些点”的结果。解决办法很直接状态定义不变转移方程不变只是在填 dp 表时额外判断一下如果当前格子是障碍物就让 dp[i][j]0表示这个格子不可达。int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int n obstacleGrid.size(); int m obstacleGrid[0].size(); vectorvectorint dp(n, vectorint(m, 0)); dp[0][0] obstacleGrid[0][0] ? 0 : 1; for (int i 0; i n; i) { for (int j 0; j m; j) { if (obstacleGrid[i][j]) 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] 要先单独判断如果起点本身就是障碍物那直接返 0根本没路可走。第二初始化第一行和第一列时不能无脑赋 1。因为如果第一行的第 k 列是障碍物那么它后面的格子全部不可达即使不是障碍物也到不了。比如第一行第 1 列是障碍那么第 2 列无论是不是障碍都无法到达因为它无法绕回第一行。上面这段代码因为采用了“每个格子都遍历 累加上方和左方”的写法天然规避了这种边界问题——障碍物位置的 dp 值为 0它自然无法往后传递 1。这种“把边界处理和转移统一起来”的写法是我比较推荐的它比单独写初始化循环再填表更不容易掉坑。初学者如果踩了“第一行障碍物后面还是输出 1”的 bug多半就是因为初始化时直接把整行赋了 1。4.2 输出一条具体路径pre数组回溯法有时候题目不满足于让你输出路径数量还会让你输出一条实际的行走路线比如用字符串“R”表示向右、“D”表示向下。这时候光有 dp 表不够还得额外开一个 pre 数组记录每个格子是从哪个方向走过来的。我用字符 U 表示从上方来用 L 表示从左方来vectorvectorchar from(n, vectorchar(m, )); for (int j 0; j m; j) { dp[0][j] 1; from[0][j] L; } for (int i 0; i n; i) { dp[i][0] 1; from[i][0] U; } for (int i 1; i n; i) { for (int j 1; j m; j) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; from[i][j] (dp[i - 1][j] dp[i][j - 1]) ? U : L; } } string path ; int i n - 1, j m - 1; while (i 0 || j 0) { if (from[i][j] U) { path D; i--; } else { path R; j--; } } reverse(path.begin(), path.end());这里最容易绕晕的点是反向回溯的字符对应关系。from[i][j]U 表示“我是从上方 (i-1,j) 走到当前格子的”既然走到这个格子需要向下移动所以回溯时往字符串里记录的是反向子的路径字符 D也就是真实的“向下”。因为我是从终点往起点回溯的最后得到的路径是逆序的所以结束时需要用 reverse 反转。如果你觉得记 U/D 的对应关系容易混乱也可以在 from 数组里直接存真实移动方向比如 from[i][j]D 表示从 (i-1,j) 向下来到当前格回溯时记录的也是 D这样字符就不需要反转了。但不论哪种写法核心思想都是从终点出发依赖记录的前驱信息一步一步走回起点最后反转成从起点到终点的路径。4.3 带权重的方格最小路径和问题与通用DP框架如果把每个格子当成带有权重的点走一个格子就累加对应权值问从左上到右下的最小权值和这就是另一个经典变体——最小路径和问题。这个题的转移方程也几乎一样只不过把“加方案数”换成“取最小”dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]含义非常直观到达当前格子的最小代价等于从上方下来和从左方过来这两者中较小的一个再加上当前格子的权值。边界上也没有第二个方向只能一路累加。int minPathSum(vectorvectorint grid) { int n grid.size(), m grid[0].size(); vectorvectorint dp(n, vectorint(m, 0)); dp[0][0] grid[0][0]; for (int j 1; j m; j) dp[0][j] dp[0][j - 1] grid[0][j]; for (int i 1; i n; i) dp[i][0] dp[i - 1][0] grid[i][0]; for (int i 1; i n; i) { for (int j 1; j m; j) { dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } return dp[n - 1][m - 1]; }这个题目同样可以用一维滚动数组优化思路和路径计数版完全一致只是把 dp[j] dp[j-1] 换成了 dp[j] min(dp[j], dp[j-1]) grid[i][j]。所以你看同样一个格子路径问题的框架改改状态定义就能适配不同问题这就是 DP 模板的真正价值。4.4 面对变体时怎么快速套上DP框架我总结了一个自己套DP变体时的固定流程分享给你。第一步先定义 dp[i][j] 的语义想清楚是“方案数”还是“最大/最小代价”。第二步思考到达 (i,j) 的最后一步有哪几种可能。方格前进类题目基本只有两个从上方来或从左方来。如果不是这两个方向也要先想清楚移动规则。第三步写出转移方程。方案数就用加法最优化就用 min/max然后再考虑是否需要额外信息。第四步处理边界。起点怎么初始化第一行第一列怎么推导有无障碍物这些都是边界工作的核心。第五步根据空间复杂度要求决定要不要滚动数组优化。这套流程对绝大多数“二维网格移动”的题目都适用包括后续你可能遇到的“不同路径 III”“骑士最短路径”等变体核心思想都是相通的。5. 实战中必踩的坑与面试表达建议5.1 三个最常见的边界错误第一个错误是我反复提到的障碍物题目里第一行或第一列初始化时无脑全填 1。一旦道路被障碍物切断后面的格子实际上不可达。正确的处理方式是让不可达的 0 沿着边界一路传导下去。第二个错误是数组下标越界却不自知。n 和 m 如果都等于 0或者网格为空直接访问 dp[n-1][m-1] 就会崩溃。实际做题时可以先判空如果 n0 || m0 直接返回 0。第三个错误是忘记给 dp 数组整体清零或者初始化时只清了一部分。在 C 的 vector 初始化里这个问题不常见但在手动开数组的场景下经常踩。养成“声明数组后用循环或构造函数统一初始化”的习惯能省很多调试时间。5.2 大数溢出、取模以及一维数组遍历方向路径数量随着 n、m 增大膨胀速度非常惊人。当 nm100 时路径数已经是一个天文数字远超 int 甚至 long long 的表示范围。所以有些题目会在题干里要求结果对某个大质数取模例如对 1e97 取模。遇到这种题转移方程里的加法要对模数取余防止中间结果溢出。我见到过不少新手在取模问题上只对最后答案取模忽略了中间 dp 值的累加过程。dp 表填到后面早就溢出变成负数了最后取模自然得不到正确答案。正确的做法是在每次加法时都取模dp[i][j] (dp[i - 1][j] dp[i][j - 1]) % MOD;另一个要反复强调的是一维滚动数组的遍历方向。前面说过从左往右遍历时dp[j] 表示上一行、dp[j-1] 表示当前行两者相加才是正确结果一旦从右往左dp[j-1] 还没更新用的还是上一行的值结果就错了。这个细节没有任何推理捷径唯一的办法是理解 dp 数组里的“行语义”然后在代码里写注释提醒自己。5.3 面试中怎么把动态规划思路讲清楚面试官问这道题考察的往往不是你会不会背代码而是你能不能把“为什么这样定义状态、为什么转移方程是这样”讲明白。我建议按这个顺序说先描述清楚问题明确移动规则然后说“我们把 dp[i][j] 定义为……”。接着解释最后一步因为只能向右和向下所以 (i,j) 只能由上方和左方转移过来转移方程就是加法关系。再解释边界第一行第一列只能沿一个方向走所以初始化为 1。最后如果面试官追问空间优化再主动提一维滚动数组并顺带说明为什么要从左到右遍历。整个过程最忌讳上来就掏代码。先在白板上写状态定义和转移方程让面试官看到你的思考轨迹。如果能顺手演算一个 3×3 的 dp 表证明你的方程在具体例子上成立基本就稳了。另外如果面试官问“这个题不用 DP用组合数也行你怎么看”可以大方的承认组合数在无障碍物的情况下更高效然后补充说明一旦题目加入障碍物、权重等限制条件组合数公式的复杂度会急剧上升DP 框架则能平滑扩展这也是面试官考察这道题的根本原因。这样回答既展示了数学功底又体现了算法思维的系统性。说到底n*m 方格前进问题之所以经典不是因为它的代码有多难写而是因为它把动态规划最核心的“状态定义、转移方程、边界处理、空间优化”四个环节完整地演示了一遍。后面不管你遇到的是障碍物版本、最小路径和版本还是更复杂的“最多经过 K 次转向”版本只要愿意回到“最后一步从哪来”这个起点去分析就能顺着同一套思路往下走。我自己最初在组合数公式上吃过亏后来才想明白与其背一个只适用于特定场景的数学公式不如彻底掌握一个能应对各种改版的算法框架。希望这篇拆解能帮你在动态规划这条路上少走几次弯路。