第一次见到“不同路径”这道题时我的第一反应是暴力递归从左上角开始每次分叉出“向下”和“向右”两个选择走到终点就计数。代码确实能跑样例也能过可网格稍微大一点就卡到怀疑人生。后来才想明白这题真正想让人练的不是枚举所有路线而是把“路线数量”拆成子问题——也就是 DP 里的状态定义与状态转移。这篇我会从暴力递归讲起一路聊到二维 DP、一维空间优化、组合数学解法最后说说这类棋盘路径题怎么举一反三。适合刚学动态规划不久、想彻底搞懂这道题的人也适合想借这道题复习“滚动数组”思路的老手。1. 题目到底在问什么从“枚举路线”到“填表格”1.1 先写一版能跑的暴力递归题目本身一句话就能描述有一个m行n列的网格机器人从左上角出发每次只能向下或者向右走一步问到达右下角一共多少条不同路径。我第一次实现用的递归大概长这样def unique_paths(m, n): # 如果只剩一行或一列那只能直走路径数为 1 if m 1 or n 1: return 1 # 到达当前点的最后一步要么从上面来要么从左边来 return unique_paths(m - 1, n) unique_paths(m, n - 1)这个思路本质上是从终点往回推我要知道m * n网格左上到右下的路径数只需要知道(m-1) * n和m * (n-1)两种子网格的答案再把它们加起来。对于3 * 7这种小网格它能算出 28。但你再试试10 * 10运行时间肉眼可见地变长换成20 * 20基本就没法等了。原因是递归树里大量子问题被重复计算。比如unique_paths(3, 5)会出现在很多分支里每次都要重新递归一遍计算量指数爆炸。1.2 重叠子问题递归慢不是因为“走法多”而是因为“重复算”“不同路径”这种题能上 DP最关键的一点就是它有重叠子问题。你从不同分支往终点回溯时会反复碰到同一个“位置状态”。比如到达某个格子需要几步这个值不管从哪条先前的路线来看都是一样的。于是自然想到记忆化把已经算过的子问题存下来遇到就直接返回。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)用(i, j)表示从左上角走到第i行、第j列的路径数。当i 0或者j 0时只有一条路一直在第一行往右走或者一直在第一列往下走。到这里暴力递归才进化成“带缓存的递归”。但带缓存的递归本质上还是递归而很多情况下显式地按顺序填一张表思路更清晰也更容易优化。于是就有了最经典的二维 DP 解法。2. 二维 DP 表状态、转移、边界是同一件事2.1 状态定义和转移方程二维 DP 先要明确一件事dp[i][j]到底代表什么。我用的是 0 起点坐标网格左上角是(0, 0)右下角是(m-1, n-1)。定义dp[i][j]从左上角走到格子(i, j)的不同路径数。接下来推导状态转移。机器人从(i, j)往回看它能走到这里最后一步只有两种可能从上方(i-1, j)往下走一步从左侧(i, j-1)往右走一步。因为“从上方来”和“从左侧来”是两种互不相交的走法不存在重复所以直接相加dp[i][j] dp[i-1][j] dp[i][j-1]这就是状态转移方程。它成立的前提是题目限定了“只能向下或向右”。如果允许回头走这个方程马上失效因为可能绕圈子。初始条件也同样直接第一行的格子只能从左往右一直走所以整行都是 1第一列的格子只能从上往下一直走所以整列也都是 1。dp[0][0]是起点路径数为 1。2.2 手填一张 3×7 的表光看公式可能还是有点抽象我建议你拿纸笔填一次。下面是一张3 * 7的 DP 表行是i列是j1111111123456713610152128怎么填的先写第一行和第一列全是 1。然后(1,1)是dp[0][1] dp[1][0] 1 1 2(1,2)是dp[0][2] dp[1][1] 1 2 3。每一格都等于“上面一格 左边一格”。最后右下角是 28这就是3 * 7的答案。这个填表过程其实比任何文字描述都更能建立直觉所谓 DP就是保证每一格只算一次并且每一格依赖的格子都已经在它之前算好了。2.3 二维 DP 完整代码和常见边界坑直接上代码def unique_paths(m, n): # 第一行第一列都初始化为 1 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] * n for _ in range(m)]就把第一行和第一列都填好了所以循环从(1, 1)开始不用额外判断边界。这里必须提一个 Python 新手非常容易踩的坑不要用[[1] * n] * m来初始化二维数组。[[1] * n] * m创建的是同一行对象的 m 个引用你改dp[0][1]会发现整列都跟着变因为它们在内存里是同一个 list。正确写法是[[1] * n for _ in range(m)]每一行独立创建。如果不小心把 i 和 j 弄反代码也不会报错但结果通常不对。建议在写循环时先固定一下语义外层循环一定是对应到“行”也就是第一个维度。3. 一维数组优化空间从 O(mn) 降到 O(n)3.1 为什么只需要保留一行二维 DP 的空间是O(m*n)。对100 * 100的网格来说也就是一万个整数不算多。但刷题和面试里经常会被追问一句能不能把空间优化一下能。核心原因是dp[i][j]只依赖两个位置一个是上一行的dp[i-1][j]一个是当前行左侧的dp[i][j-1]。回忆一下填表过程第 i 行从左往右填的时候需要的“上方格子dp[i-1][j]”其实就在上一行数组的同一位置需要的“左侧格子dp[i][j-1]”是当前行刚刚计算出来的新值。也就是说我不需要保留整个二维表只需要一个长度为 n 的一维数组滚动更新即可。这个优化思路在动态规划里很常见叫“滚动数组”。很多博客叫它“状态压缩”但本质就是发现当前状态只和最近一层有关于是把该丢的历史数据丢掉。3.2 单数组原地更新顺序为什么必须从左到右一维数组的写法有很多我推荐这种最直接的def unique_paths(m, n): dp [1] * n # 第一行 for _ in range(1, m): for j in range(1, n): dp[j] dp[j] dp[j - 1] return dp[-1]初始化的[1] * n相当于填好了第一行。接下来每一轮外层循环相当于“基于上一行推出当前行”。关键点在这内层循环执行dp[j] dp[j] dp[j - 1]时dp[j]在更新前存的是上一行的值也就是dp[i-1][j]dp[j-1]在当前行已经更新过了所以就是dp[i][j-1]。两者相加恰好等于当前行的dp[i][j]。所以内层循环必须从左向右遍历。如果从右往左更新dp[j-1]还是上一行的旧值结果就会变成“左上角一格 左上角更左一格”完全错掉。还记得背包问题里“倒序遍历”是为了避免同一物品被重复使用吗这里正相反我们需要的就是左侧的新值所以必须正序。同样是“一维数组覆盖”方向性完全取决于你依赖的是旧数组里的哪个值。这个对比非常值得记住。3.3 手算验证一维数组还是拿3 * 7举例。一开始dp [1, 1, 1, 1, 1, 1, 1]这代表第一行。外层循环第一次计算第二行j1dp[1] dp[1] dp[0] 1 1 2j2dp[2] dp[2] dp[1] 1 2 3j3dp[3] dp[3] dp[2] 1 3 4...更新完得到[1, 2, 3, 4, 5, 6, 7]正好对应二维表第二行。外层循环第二次计算第三行j1dp[1] 2 1 3j2dp[2] 3 3 6j3dp[3] 4 6 10...最后得到[1, 3, 6, 10, 15, 21, 28]右下角dp[-1]就是 28。这个优化后复杂度是时间仍然是O(m*n)因为每个格子还是计算了一次空间从O(m*n)降到了O(n)。另外如果你不想在单数组上纠结原地覆盖也可以先写两个数组pre [1] * n cur [1] * n for _ in range(1, m): for j in range(1, n): cur[j] pre[j] cur[j - 1] pre cur[:] return pre[-1]这个版本更好理解但空间略多一点。面试时可以先说双数组版再优化成单数组版逻辑上更顺。4. 组合数学解法C(mn-2, m-1) 是怎么来的4.1 把路径翻译成“一步序列”走到右下角总共必须向右走n-1步向下走m-1步总步数固定是mn-2。任意一条路径其实就是一个由“D”Down向下和“R”Right向右组成的长为mn-2的序列。比如 3 行 7 列从左上到右下可以是RRRRRRDD也可以是RDRRRRRD等等。序列里一共有m-1个 D 和n-1个 R。路径数量就等价于从长度为mn-2的位置里选出m-1个位置放 D剩下的位置自动放 R。因此答案是组合数C(mn-2, m-1)也可以写成C(mn-2, n-1)结果一样。直观理解不是直接搞排列因为 D 和 D 之间、R 和 R 之间互换后是同一条路径所以只能用组合数不能把所有 D 和 R 当作互不相同的东西去排列。4.2 Python 实现和手写组合数的避坑写法如果直接用 Python 标准库一行就能算from math import comb def unique_paths_comb(m, n): return comb(m n - 2, m - 1)comb是 Python 3.8 之后的标准库直接用没问题。但在很多面试场景里面试官并不满足于你调库还会让你手写一个不溢出的组合数。这时可以用“边乘边除”的方法def unique_paths_comb_manual(m, n): total m n - 2 k min(m - 1, n - 1) res 1 for i in range(1, k 1): res res * (total - k i) // i return res这里取k min(m-1, n-1)是为了少循环几次。原理是C(total, k) (total-k1) * (total-k2) * ... * total / (1*2*...*k)因为组合数一定是整数每一步乘完再整除都能保证整除不会产生小数误差。这个“边乘边除”的手法在很多计数类题目里都能用比先算出大分子再除大分母要稳妥得多。如果用 C要注意int在中间乘法时可能溢出。稳妥做法是用long long并且题目通常保证最终答案在 32 位整型范围内但中间结果可能很大res * (total - k i)这一步最好用 64 位。4.3 组合数解法和 DP 究竟是什么关系我最早以为组合数学解法和 DP 是两个完全不同的东西后来才意识到它们说的是同一件事。回到二维 DP 表。如果用 0 起点坐标从左上角到(i, j)一共要走ij步其中有i步向下、j步向右。路径数应该等于C(ij, i)。也就是说dp[i][j]这个表格本身就是一张“杨辉三角式”的组合数表dp[0][0] C(0,0) 1dp[1][1] C(2,1) 2dp[2][6] C(8,2) 28所以 DP 的累加过程本质上就是在用递推方式计算组合数。组合数公式是闭式解DP 是递推解两者答案必然一致。既然如此那是不是以后直接用组合数公式就行也不是。如果题目里加了障碍物比如地图中间有几格不能走组合数就没法一步到位了需要排除所有穿过障碍物的路径计算会很复杂。而 DP 只要在转移时跳过障碍格就能自然处理。这也是为什么面试更看重 DP 思路。5. 触类旁通障碍物版本、状态压缩和实战排错经验5.1 加几个障碍物之后DP 怎么改“不同路径”最常见的变体是网格里某些格子是障碍物机器人不能走到这些格子上。此时 DP 状态定义不变但转移要加判断如果(i, j)是障碍物那么dp[i][j] 0表示没有路径能到达这个点如果不是障碍物dp[i][j] dp[i-1][j] dp[i][j-1]第一行和第一列也要跟着改如果第一行某个位置是障碍物那么它自己以及它右侧的所有格子都不可达第一列同理。代码可以写成def unique_paths_with_obstacles(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] for i in range(m): if grid[i][0] 1: break dp[i][0] 1 for j in range(n): if grid[0][j] 1: break dp[0][j] 1 for i in range(1, m): for j in range(1, n): if grid[i][j] 1: dp[i][j] 0 else: dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]这个版本同样可以做一维空间优化但不能再用dp [1] * n初始化了因为障碍物可能出现在第一行和第一列需要单独处理边界。5.2 什么时候能用滚动数组什么时候不能通过这道题你可以总结一个判断标准当前格子的状态更新依赖的是上一层完整数据还是更早之前的斜向数据。如果只依赖“上一行同一列”和“当前行左侧”就可以用一个一维数组滚动。如果依赖“上一行左侧”或“左上方”你在覆盖时就拿不到旧值了可能需要两个一维数组或者临时变量保存被覆盖前的值。比如路径题里如果允许斜着移动情况就会变复杂如果变成“到达每个格子有不同代价求最小代价”类似的方法依然有效因为每个格子的最优解也只依赖上方和左侧。所以刷 DP 题时没必要死记“这道题用滚动数组那道题不能用”。你只要画一遍依赖关系图马上能判断能不能压。这也是“不同路径”作为入门题的价值它把 DP 分类里最经典的一类模型讲透了。5.3 几个值得记住的经验教训我刷这道题和后面变体时踩过的坑基本集中在三处第一Python 二维数组初始化。[[1] * n] * m会让每一行共享内存这是最常见的隐蔽 bug。我身边有同学因为这个错误查了半小时。建议多写[[0] * n for _ in range(m)]这种列表推导式。第二坐标方向搞反。递归版本和循环版本的状态定义要一致。如果你把dfs(i, j)定义成“从 (i,j) 走到右下角有多少种”那转移方向会完全反过来基准条件也变成边界为最后一行或最后一列。两个定义都能做对但混着用必然出错。第三一维数组的更新顺序。看到“一维数组原地更新”先想清楚每个值在被覆盖之前是哪个状态、覆盖之后又变成了哪个状态。就拿本题来说dp[j]在更新前是上一行的上方格子更新后是当前行的当前格子。从左到右更新当前行左侧的新值才能被后面的位置利用。这一步想明白了以后遇到类似滚动数组题都不会慌。最后说一个我自己的心得遇到路径计数题先不要急着套模板而是在草稿纸上把3 * 3或者3 * 7的小表手填一遍。填完你就会发现所谓“状态转移”无非就是“每个格子的值等于上方加左侧”。这个习惯比背十道题答案都管用。