1. 题目到底在问什么先理解“n*m方格前进问题”动态规划是算法面试里绕不开的一块内容而“n*m方格前进问题”差不多是动态规划里最经典的入门题型之一。很多人在网上看了一堆动态规划的教程什么状态转移、最优子结构、重叠子问题名词背了一大堆拿到这道题还是不知道从哪下手。原因很简单抽象概念听再多不如亲手把一道题从暴力递归改到动态规划来一遍完整的心智过程。这道题最常见的描述是这样一个机器人位于一个 n 行 m 列的网格左上角每次只能向右或者向下移动一步问到达右下角一共有多少条不同的路径。有些版本会加障碍物有些版本会问最短路径和但最基础、最干净的就是这个“只走右和下”的计数问题。先说结论这个问题的答案不是靠模拟一步一步走出来的而是靠“拆”。你站在任何一个格子上能走到这个格子的方式只有两种——从上面走下来或者从左边走过来。所以到达当前格子的路径总数就等于到达上方格子的路径总数加上到达左方格子的路径总数。如果你把每一个格子的这个数值都填出来最后右下角那个数字就是答案。听起来很简单对不对但这里面的“为什么能这么拆”“为什么拆完不会重复不会漏”“为什么可以用数组来存”才是动态规划的精髓。这篇文章我不打算只甩一个公式给你而是把从审题、建模、写代码、优化到踩坑的完整过程全部过一遍保证你看完之后不仅能写对这道题还能把它背上的那层皮扒干净以后遇到类似的题心里都有底。适合谁来读正在学算法的学生、准备面试的开发者、刷 LeetCode 卡在动态规划入门的同学都适合。这道题本身不难但它背后牵出的“状态定义 转移方程 初始化 遍历顺序”四件套是你之后面对所有动态规划题目的通用框架。2. 为什么暴力搜索行不通先算一笔复杂度的账很多第一次看到这道题的人第一反应是那我就用深搜 DFS 呗从起点开始每次往右或往下走走到终点就计数加一。这个思路没有错甚至在逻辑上非常直观但问题是它跑不完。2.1 暴力搜索到底会遍历多少条路径我们算一下。一个 n 行 m 列的网格从左上角走到右下角因为只能向右和向下走所以总共需要走 (n - 1) (m - 1) n m - 2 步其中向下走 n - 1 步向右走 m - 1 步。路径总数是组合数 C(n m - 2, n - 1)也就是从总步数里选出哪几步向下走。这个数涨得有多快我随手列几个值你感受一下3 行 3 列C(4, 2) 6 条5 行 5 列C(8, 4) 70 条8 行 8 列C(14, 7) 3432 条10 行 10 列C(18, 9) 48620 条15 行 15 列C(28, 14) 40116600 条18 行 18 列C(34, 17)大概 23 亿条也就是说20 行 20 列以内的网格暴力搜索就已经是亿级别的访问量了。就算每一条路径只做常数次操作跑起来也是秒级起步再大一点直接指数爆炸。面试官让你手写这道题如果丢一个 DFS 上去基本就是送人头的。2.2 重复计算是罪魁祸首暴力搜索慢不是因为“走的路径多”这个现象本身而是因为大量子问题被反复计算。什么叫重复计算你从起点出发有无数种方式走到中间某个格子 (i, j)但一旦走到了 (i, j)之后到终点的路径数其实是固定的。DFS 的做法是每一条完整路径都从头走一遍相当于同一个“从 (i, j) 到终点的路径数”被反复算了几百次、几千次。动态规划干的事情就是把这个共享的“中间结果”存下来用一次就算一次之后直接查表。这就是所谓的“用空间换时间”。明白了这一点你就知道为什么动态规划能把这个指数级的问题降到多项式级——因为整个网格一共只有 n 乘 m 个格子每个格子只需要算一次。我之前带过不少同学很多人卡住不是因为不知道状态转移怎么写而是没想明白“为什么不能直接 DFS”。我建议你从第一步开始就建立这个认知动态规划不是一种花哨的技巧它就是一种“聪明地复用中间结果”的暴力搜索。想通了这一点后面所有代码都是在给这句话做注脚。3. 核心建模状态定义、转移方程、初始化与遍历顺序动态规划的解题目套路说来说去就是四件事状态定义、转移方程、初始化、遍历顺序。这一节我把每一件都拆开讲透而且每一件都会回答“为什么”而不是只告诉你“是什么”。3.1 状态定义dp[i][j] 到底代表什么对于这道题最自然的状态定义是dp[i][j] 表示从左上角 (0, 0) 出发到达格子 (i, j) 的路径总数。这里的 i 表示行号j 表示列号范围分别是 0 到 n-1 和 0 到 m-1。下标从 0 开始还是从 1 开始纯粹是个人习惯问题。我个人更推荐从 0 开始因为和数组下标天然对齐写代码的时候少做一次转换。如果你从 1 开始状态定义就变成“到达第 i 行第 j 列的路径总数”边界条件会稍微好写一点但本质上没有任何区别。状态定义是整个动态规划题里最重要的一步比转移方程还重要。因为一旦状态定义得不好后面的转移方程怎么都推不顺。反过来状态定义好了转移方程通常是顺手写出来的。这个道理在你以后做更复杂的动态规划题时会反复应验。3.2 转移方程从哪来比到哪去更重要有了状态定义下一步就是考虑转移方程。对于当前格子 (i, j)由于你只能从上方 (i-1, j) 或者左方 (i, j-1) 走过来所以到达 (i, j) 的路径总数就是到达这两个格子的路径总数之和dp[i][j] dp[i-1][j] dp[i][j-1]这就是整道题最核心的公式。你可能觉得这也太简单了但我要提醒你一个隐蔽的点转移方向。很多人写动态规划的时候习惯性去想“从当前格子可以走到哪里”然后写出一堆“往后推”的逻辑。但动态规划的核心思维是“当前状态从哪里来”是倒着想的。这个思维差异很重要。正向推也可以做遍历顺序反着写就行但新手阶段我强烈建议统一用“从哪里来”的视角不容易漏状态、不容易乱。再补一句这道题里你只需要向右和向下走所以不会有回头路这意味着图是天然的“有向无环图”按从左到右、从上到下的顺序遍历每个格子的依赖都一定先被计算出来。这也是为什么动态规划能在这里成立。如果允许上下左右乱走那就不是计数问题而是图搜索问题了动态规划也未必适用。3.3 初始化边界值为什么是 1任何动态规划题都有边界条件这道题的边界条件非常直观第一行 dp[0][j] 的任意位置都只有一种走法能到达——就是一路向右走同理第一列 dp[i][0] 的任意位置也只有一种走法——一路向下走。所以初始化就是把 dp 数组的第一行和第一列全部填成 1。严谨一点说dp[0][j] 1对所有 0 j mdp[i][0] 1对所有 0 i n这一步经常被忽略但它的重要性不亚于转移方程本身。我自己踩过的一个坑是把起点 dp[0][0] 设成 0结果整个数组后面全错了。你仔细想想机器人一开始就在起点到达起点的路径只有一种就是“什么都不做”所以 dp[0][0] 必须等于 1。这是个很小的细节但能卡住很多人。3.4 遍历顺序为什么这样遍历换顺序行不行这道题的遍历顺序非常朴素从左上角开始一行一行往下扫每一行里从左往右扫。核心原则只有一个——计算 dp[i][j] 的时候它依赖的两个格子 dp[i-1][j] 和 dp[i][j-1] 必须已经算完了。只要你确保这一点遍历顺序其实可以变。比如说你可以按列扫先从左往右一列一列地处理每一列里从上到下。但如果你先算右下角再算左上角那就违背了依赖关系算出来的值全是错的。有一个小细节值得说一下在嵌套循环里外层循环行、内层循环列是最常见的但这只是因为这样写符合阅读习惯。换成外层循环列、内层循环行同样正确。真正重要的不是循环怎么写而是“依赖的格子是否先被算出来”这个隐含约束。在你以后遇到带障碍物、带权重、带方向限制的变体题时这一步的思考会救你很多次。4. 完整实操从暴力递归到四套代码的进化之路理论知识说完了现在进入实操。我会按“暴力递归只讲思路→ 记忆化搜索 → 二维 DP → 滚动数组优化 → 组合数学公式”这个顺序带着你把代码一步一步进化。每一步都有清晰的代码示范和踩坑记录你可以直接照着敲。4.1 暴力递归版本先让思路跑通暴力递归的核心逻辑前面已经说过定义一个函数 dfs(i, j) 表示从起点到 (i, j) 的路径数那么 dfs(i, j) dfs(i-1, j) dfs(i, j-1)边界是当 i 0 或 j 0 时返回 1。代码写出来是这样的def dfs(i, j): # 边界第一行或第一列只有一种走法 if i 0 or j 0: return 1 return dfs(i - 1, j) dfs(i, j - 1) def unique_paths_dfs(n, m): return dfs(n - 1, m - 1)这个版本能出正确结果但只能处理很小的 n、m比如 5 乘 5、7 乘 7 这种。一旦到 15 乘 15等待你的就是漫长到让人怀疑人生的运行时间。我在实际练习的时候用这个版本跑过 18 乘 18大概跑了半分钟21 乘 21 直接等到崩溃。为什么可以用一棵递归树来解释dfs(3, 3) 调用了 dfs(2, 3) 和 dfs(3, 2)而这两个又会共同调用 dfs(2, 2)子问题被重复计算导致整体时间复杂度是 O(2^(nm)) 级别的指数爆炸。4.2 记忆化搜索给递归加一个缓存既然重复计算是罪魁祸首那最直接的优化就是加缓存。把已经算过的 dfs(i, j) 存起来下次再要直接查表不再往下递归。这就是记忆化搜索也叫自顶向下的动态规划。from functools import lru_cache lru_cache(None) def dfs(i, j): if i 0 or j 0: return 1 return dfs(i - 1, j) dfs(i, j - 1) def unique_paths_memo(n, m): return dfs(n - 1, m - 1)加了这一行缓存之后每个 (i, j) 只会被计算一次时间复杂度和空间复杂度都降到了 O(n*m)。这就是动态规划的雏形——虽然它没有显式地写数组但本质上是“用空间换时间”的思想。我个人很喜欢记忆化搜索因为它写起来非常接近人类直觉不需要想遍历顺序。很多复杂动态规划题尤其是区间 DP 或者树形 DP直接用记忆化搜索反而比递推 DP 好写得多。但面试的时候如果你能主动给出从暴力到记忆化再到 DP 的演进路径会显得你对整个思路的理解非常清晰。4.3 经典二维 DP面试最常写的版本记忆化搜索虽然直观但它有递归调用栈的额外开销而且 Python 的递归深度限制在某些极端情况下也会成为问题。面试官多半会希望你写出显式的递推版 DP也叫自底向上的动态规划。这一步我们把思路从“从终点往前递归”切换成“从起点往后递推”。def unique_paths_dp(n, m): # 初始化一个 n 行 m 列的全 0 二维数组 dp [[0] * m for _ in range(n)] # 第一列只有一种走法 for i in range(n): dp[i][0] 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]代码本身不难但有几个细节值得你注意。第一是创建二维数组的方式Python 里[[0] * m] * n是错误示范因为这样每一行其实是同一个列表的引用改一行全跟着变必须用列表推导式[[0] * m for _ in range(n)]。第二是循环的起点从 1 开始因为边界第 0 行和第 0 列已经在初始化时被填好了。第三是返回值dp[n-1][m-1]就是右下角的路径总数千万别手滑写成dp[m-1][n-1]这种低级错误我见过不止一次。为了让你确认自己写对了我放一个 3 行 3 列的 dp 表填充结果位置列0列1列2行0111行1123行2136右下角是 6也就是 3 乘 3 网格的答案。你自己用手推一遍这个表能顺下来就说明这道题真的理解了。4.4 滚动数组优化空间复杂度从 O(n*m) 降到 O(m)二维 DP 已经足够应付大多数场景了但如果你去刷题可能会看到空间优化的版本。这里有一个非常优雅的观察计算第 i 行的 dp 值只用到第 i-1 行的数据再往上的行就再也用不到了。所以不需要保留整个二维表只需要保留一行就够了。这就是传说中的滚动数组。代码如下def unique_paths_optimized(n, m): # 只保留一行状态 dp [1] * m # 从第二行开始逐行更新 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] dp[j-1] 里的 dp[j] 和 dp[j-1] 分别代表什么其中 dp[j] 在更新前是上一行同一列的值也就是“从上方来的路径数”dp[j-1] 在更新后是当前行左边格子的值也就是“从左方来的路径数”。两者相加正好就是当前格子的路径总数。这个优化能把空间复杂度从 O(n*m) 降到 O(m)。如果题目同时要求 n 和 m 很小这不算什么但当网格变大比如 10000 乘 10000显式开辟一个亿级元素的二维数组就很不现实滚动数组就非常实用了。我在实际教学里发现有不少同学能理解二维 DP但看不懂滚动数组。我给他们建议是不要“读”这段代码而是拿笔在纸上画一个只有一行的表格把每次循环更新后数字的变化过程写出来多写两轮就恍然大悟了。空间优化是最容易出 bug 的地方核心理解点在于“更新时机”。4.5 组合数学解法这道题的另一种身份这道题本质上和组合数学是相通的。我们前面说过机器人一共要走 n m - 2 步其中向下走 n - 1 步向右走 m - 1 步。路径总数为从这 n m - 2 步中选出 n - 1 步作为向下走的组合数也就是 C(n m - 2, n - 1)。用 Python 可以直接这样写import math def unique_paths_math(n, m): return math.comb(n m - 2, n - 1)时间复杂度可以做到 O(min(n, m))空间复杂度 O(1)比动态规划更快更省。但你要注意这个解法只适用于“没有任何障碍物”的纯粹版题目。一旦题目加了障碍物组合数公式就不能直接套了这时候动态规划才是通用解法。那为什么还要学动态规划直接用组合数不香吗因为这道题是动态规划练手的敲门砖你的目标不是只解决这一道题而是通过它掌握一种能解决一大类问题的思维工具。面试官想考察的也不是你会不会算组合数而是你有没有能力把一个看似复杂的问题转化成子问题逐步求解。5. 常见问题与排查技巧我踩过的坑都在这里这一节是我最想写的内容。网上各种教程都在讲“怎么写对”但很少讲“写错了怎么排查”。我把这些年刷题和带新人过程中最常见的错误整理成了一份速查表每一个都是真人真事。5.1 溢出问题小方格也会撑爆整数范围这道题看起来就是几十、几百的数字很多人根本不会想到溢出问题但真实情况是一个稍微大一点的网格路径数会涨得超乎你想象。我算过几个具体数字10 行 10 列48620 条15 行 15 列40116600 条20 行 20 列35345263800 条25 行 25 列16123801841550 条30 行 30 列30067266499541040 条30 行 30 列的时候答案已经超过 3 千万亿了。如果用 C 写int 类型 4 字节最大才 21 亿左右跑到 15 行左右就开始溢出。Java 的 int 也一样。C 要用 long longJava 要用 long因为 25 行 25 列的答案超过 16 万亿37 行 37 列的答案超过 9 千亿亿连 long long 都快撑不住。Python 在这一点的优势是巨大的整数可以无限大不用考虑溢出。我建议你在刷这道题之前先去查一下目标语言里每种整数类型的范围然后问自己一句n 和 m 最大可能是多少如果题目没有给范围拿 long 是最稳妥的选择。5.2 1x1、1xn、nx1 的边界情况你敢拍胸脯吗一道题的正确性不仅体现在常规数据上更体现在边界数据上。很多隐性 bug 都是在边界处暴露的。1 行 1 列只有 1 个格子起点就是终点路径数为 1。用 DP 跑一遍dp[0][0] 初始化为 1返回 1没问题。1 行 n 列只能一直向右走只有一条路径。dp 数组第一行全为 1返回 1没问题。n 行 1 列同理只有一条路径。这些边界情况看着简单但如果你在初始化时把 dp[0][0] 漏掉了或者在返回写错了行列下标哪怕题目给的范围是 1 n, m 100你的答案也会偏移。所以写完代码后第一件事就是用边界用例自测三连1x1、1x100、100x1。还有一个小技巧题目里如果 n 和 m 可以等于 0本质上就是空网格这时候应该返回 0 而不是 1。虽然大多数题不会这么出但你多考虑一层写出来的代码就多一分健壮性。5.3 调试技巧把 dp 表打出来比什么 log 都管用我在调试动态规划题的时候有一个习惯跑完循环之后把整个 dp 表 print 出来看一遍。这个习惯帮我发现了无数次灵异 bug。举个例子如果你写的是二维 DP可以加一行调试代码for row in dp: print(row)看输出结果是否符合预期。以 3 行 3 列为例正确的表应该是第一行和第一列全 1中间按“上 左”递推。如果你的表中出现了类似 [1, 1, 1], [1, 2, 3], [1, 3, 9] 这样的结果说明问题出在循环内部——右下角的 9 意味着你把 dp[i][j-1] 和 dp[i-1][j] 乘起来了而不是相加。可视化调试对我来说就像给程序照 X 光比任何断点调试都要直观。如果你遇到滚动数组版本看起来总是不对也建议先回到二维 DP 版本打印出完整表格确认逻辑无误后再手动追踪一遍滚动数组的每一步更新。新手最忌讳的就是在版本之间跳来跳去却从不打印中间结果。5.4 审题坑坐标从 0 开始还是从 1 开始还有一个容易被忽略的坑是坐标系的歧义。有的题描述会说“位于第 1 行第 1 列”这时候如果你直接拿数组下标 0 去对齐初始化部分会出问题。遇到这类输入建议在代码开头先做一步坐标转换把 1-based 的输入转成 0-based避免后续大量 1、-1 的混淆。我自己的习惯是状态定义里写清楚“dp[i][j] 表示从起点到达第 i 行第 j 列”然后无论输入是什么形式第一步统一减一。这样思路不容易乱歧义只存在于一处而不是散落在整个代码里。6. 从一道题到一类题这个模板能打多少变体动态规划最迷人的地方不在于你会用这个套路解这一道题而在于“状态定义 转移方程 初始化 遍历顺序”这四板斧换着花样能打下一大片题目。这道 n*m 方格前进题就是那个最好的出发点。6.1 变体一带障碍物的路径数如果网格里某些格子有障碍物不能走怎么办转移方程几乎不用大变只要当前格子是障碍物就令 dp[i][j] 0否则还是 dp[i][j] dp[i-1][j] dp[i][j-1]。初始化时也要注意如果第一行或第一列里有一个障碍物那它后面所有的格子都到不了了都应该保持 0。核心区别就一句话正常情况下“上方值加左方值”碰到障碍物直接置零。很多刚学完基础版的同学做这道变体时会被“边界行遇到障碍物”搞晕。最稳妥的理解方式是障碍物把它所在的行和列切断了所有依赖它的格子全部失效。拿 1 行 4 列、第 2 列是障碍物来举例结果应该是 [1, 0, 0, 0]第 3 列第 4 列都到不了。6.2 变体二找一条最小路径和如果把“计数”改成“求最小路径和”每一格还有一个权重值这就是 LeetCode 第 64 题。转移方程变成dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])意思是到当前格子的最小代价等于当前格子的代价加上从上方或左方过来的较小代价。这次的初始化思路也不一样第一行只能从左往右累加第一列只能从上往下累加。从这个变体你能明显感受到动态规划的四步框架完全没变变的只是“转移方程里是加号还是取 min”这一处细节。6.3 变体三不只求数量还要输出完整路径如果题目要求你输出每一条路径这就要回到回溯/DFS 的思路因为路径数量可能是指数级的不可能用动态规划直接生成所有路径。动态规划的价值在于快速求得数量而回溯的价值在于枚举具体方案。两种方法各有适用场景理解它们的分工比盲目背模板重要得多。我在实际面试中见过一个很有意思的追问“既然你已经知道有多少条路径了能不能反向推出其中某一条”这时候你可以从终点倒推如果 dp[i-1][j] 大于 dp[i][j-1]说明到达当前格子的路径更多来自上方就往回走到上方不断回溯直到起点就能还原出一条路径。这种“倒推路径”的思路在很多动态规划题里都有用比如最长公共子序列的输出。6.4 变体四不同起点和终点的大网格还有一类题不是从 (0,0) 走到 (n-1,m-1)而是给定多个起点和终点问你某两点间有多少条路径。做法是在 dp 表上做 mark把所有起点初始化为 1然后按同样规则递推终点处取值就是答案。本质上动态规划表的信息是可以复用的提前算好一整张表后续任何查询都可以 O(1) 完成。所以你现在应该能理解为什么那么多算法博主都说“动态规划是一种思想不是一道题”。方格前进这道题就是你进入这个思想的第一个台阶。7. 我个人在实际操作中的一点体会写了这么多最后聊几句题外话。如果你刚接触动态规划我建议你千万不要只抄代码。拿到这道题先自己画一个 5 乘 5 的表格用手推一遍 dp 值再用暴力递归写一遍哪怕慢也要跑通然后加记忆化最后改成滚动数组。这个过程完整走下来你对动态规划的“重叠子问题”和“空间换时间”会有非常直观的感受。我见过太多人刷题只求“AC”代码是抄来的思路是背的结果换一道题又不会了。另外一个很实用的建议多问自己“为什么”。为什么 dp[i][j] 是上方加左方而不是上方乘左方为什么边界是 1 而不是 0为什么滚动数组更新时 dp[j-1] 已经是当前行而不是上一行这些“为什么”每个都值得花时间去想清楚。想通一个比你多刷十道题更有用。最后再分享一个小技巧这道题的滚动数组优化版本代码只有几行特别适合拿来当默写题用来检验自己在面试高压环境下还记不记得动态规划的核心框架。如果面试紧张到只能写出二维 DP 版本也没关系先答对再谈优化一步一步来面试官更看重你的思考过程而不是最终答案。