企业官网建设流程全解析

刷过LeetCode的朋友应该都见过这道题——62 不同路径，标签是“中等”，考察的却是动态规划里的基本功。很多人在做这道题的时候，第一反应是“这有什么好DP的，直接深度优先搜不就行了”，结果写出来要么超时，要么边界条件留下一堆隐患。其实这道题看起来简单，但里面的状态设计、滚动数组优化、组合数学视角，每一个点都能在面试时成为加分项。

这个题目适合两类人看：一类是刚开始接触动态规划，想通过一道中等难度题目搭建DP思维框架的新手；另一类是已经能写出递归或二维DP，但想搞明白“为什么能用一维数组滚动省空间”“为什么可以用组合数一步算出来”这类底层逻辑的人。我会把从读题到优化、再到同类题变种的完整路径都拆开讲清楚，尽量说人话，保证你能直接抄走。

1. 题目拆解：先想清楚“为什么不能直接搜索”

1.1 题意与基本约束

题目给定一个 m 行 n 列的网格，机器人从左上角出发，每一步只能向下或者向右移动，目标是到达右下角，问总共有多少条不同的路径。m 和 n 最大是 100，输出的结果是一个整数。

题目给出的示例是 m=3、n=2，答案是 3；m=7、n=3，答案是 28。这两个数字都不大，就算你用手去枚举也能画出来，但一旦 m 和 n 接近 100，暴力枚举的路径数量是指数级的，完全不可行。

关键点在于“只能向下或向右”这个条件。很多人在这一步没有停下来想清楚：这个约束到底意味着什么？它意味着从起点到终点，任何一条路径的长度是固定的 m+n-2 步，其中必然包含 m-1 步向下和 n-1 步向右，区别只在于这 m-1 步向下出现在哪几个位置。这其实是后面组合数学解法的直接来源，也为 DP 的状态转移提供了天然依据。

1.2 为什么朴素的 DFS/BFS 在这里不是好方案

先说你可能会掉进去的坑：看到“路径数量”就去写 DFS 递归枚举所有路径。代码很短，思路也很直白：每次往右或往下走，到达终点就计数加一，越界就返回。看似没问题，但仔细分析一下复杂度就知道为什么行不通。

假设从左上角到右下角，每个格子在搜索树里可能被多条路径重复访问，路径数量本身就是一个组合数级别的结果。当 m=n=100 的时候，答案大约是几十位数字的量级，这意味着搜索会走完所有可能路径，时间绝对爆炸。而且搜索过程中还会重复计算大量重叠子问题，比如从格子 (i,j) 出发到达终点的路径数，会在不同分支里被反复求解。

相比之下，动态规划的核心思路是“记录并复用子问题的答案”。机器人走到当前格子，要么从上方来，要么从左方来，所以走到当前格子的路径数就是走到上方格子的路径数和走到左方格子的路径数之和。这个重叠子问题和最优子结构天然存在，正是 DP 趁手的场景。换句话说，这道题问的是“方案总数”而不是“具体路径是什么”，它的本质就不是让你搜索，而是让你做加法。

2. 状态设计与递推公式：一切从“格子视角”出发

2.1 dp[i][j] 的含义

很多 DP 新手最容易卡住的地方是“状态怎么定义”。这里的套路其实非常固定：DP 状态永远在描述一个“子问题”。

我们定义 dp[i][j] 表示：从左上角走到第 i 行、第 j 列的格子，总共有多少条不同的路径。

这里我用的是从 1 开始的下标，也就是左上角是 dp[1][1]，右下角是 dp[m][n]。这种定义方式最容易理解，也不容易在初始化时踩坑。当然你也可以用 0 开始的下标，即 dp[0][0] 表示左上角，两种写法各有习惯，但建议新手先用 1-based，能直观对应“第几行第几列”的日常说法。

为什么这样定义状态？因为它准确刻画了题目要我们求的东西：走到某个格子的方案数。它同时也能拆分成更小的子问题：你不可能凭空出现在某个格子上，除非你从它的上方格子走下来，或者从它的左边格子走过来。

2.2 转移方程：一条公式打天下

因为机器人只能向下和向右移动，所以到达格子 (i,j) 的前一步只有两种可能：

• 从 (i-1, j) 向下走一步；
• 从 (i, j-1) 向右走一步。

那么到达 (i,j) 的路径总数，就等于到达 (i-1,j) 的路径数加上到达 (i,j-1) 的路径数。写成公式就是：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

这个公式是整个题目的灵魂，也是后面一切优化和变体的基础。你甚至可以把它理解成一个路口的车流量统计：一个十字路口的车流量，等于从北边来的车流量加上从西边来的车流量，前提是车不会掉头、不会逆行。

初始条件也直接从这个转移方程推出：当 i=1 时，dp[0][j] 不存在，但第一行的格子只能一直向右走，所以到达第一行任意格子的路径数都是 1。同理，第一列的任意格子只能一路向下走，路径数也都是 1。于是初始化就是：

dp[1][j] = 1（第一行所有列） dp[i][1] = 1（第一列所有行）

有了初始化和递推公式，就可以一行一行往下填表，最后 dp[m][n] 就是答案。

2.3 用一张小表验证公式

光看公式不够直观，我们拿 m=3、n=3 来手动推一遍，感受一下表格是怎么从一个小三角不断累加出来的。

初始时，第 1 行全部是 1，第 1 列全部是 1。

第 2 行第 2 列：dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2 第 2 行第 3 列：dp[2][3] = dp[1][3] + dp[2][2] = 1 + 2 = 3 第 3 行第 2 列：dp[3][2] = dp[2][2] + dp[3][1] = 2 + 1 = 3 第 3 行第 3 列：dp[3][3] = dp[2][3] + dp[3][2] = 3 + 3 = 6

所以 3×3 网格的答案是 6。类比一下杨辉三角就会发现，这个 dp 表本质上就是杨辉三角的一部分，因为杨辉三角的每个数值同样是左上方和正上方两个数相加。这个直觉在后面组合数学解法里会再次印证。

3. 代码实现：从二维 DP 到一维滚动数组

3.1 最直白的二维 DP 写法

先给出最容易理解和最容易写对的版本。以 Python 为例：

def uniquePaths(m: int, n: int) -> int: dp = [[1] * n for _ in range(m)] # 把第一行和第一列都初始化为1 # 从第1行第1列开始填充（0-based 下标，即从行1列1开始） 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 就是正确的路径数。如果你不想用这个技巧，也可以画蛇添足地先单独初始化第一行和第一列，再开双层循环，但那样代码会更啰嗦，思路反而不清楚。

二维 DP 的时间复杂度是 O(mn)，空间复杂度也是 O(mn)。对于 m、n 最大 100 的数据范围，完全没有任何压力。这也是为什么很多人刷题时觉得这道题已经结束了。但面试官大概率会追问一句：能不能把空间复杂度降下来？

3.2 空间优化：为什么一个数组就能搞定

仔细观察转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]，你会发现计算第 i 行时，只用到了第 i-1 行的数据，更早的行在用完之后就永远不会再被使用了。换句话说，我们没有必要保存整个 m×n 的二维表，只需要保存“上一行”的路径数，再加上不断更新的“当前行”左侧格子数据，就足够推导出当前行的每一个值。

这里的关键在于，dp[j] 在更新之前保存的是上一行的第 j 列路径数，更新之后它变成当前行的第 j 列路径数。当计算当前行第 j 列时，dp[j-1] 已经保存的是当前行的数据，dp[j] 保存的是上一行的数据，两者相加恰好就是转移方程的右半边。这个过程叫滚动数组，也可以理解为“用一维数组滚动模拟二维状态表”。

def uniquePaths(m: int, n: int) -> int: dp = [1] * n # dp[j] 代表当前行第 j 列的路径数 for i in range(1, m): for j in range(1, n): dp[j] += dp[j-1] # dp[j] 的旧值是上一行的路径数 # dp[j-1] 是当前行已经计算好的左邻值 return dp[-1]

这个版本的时间复杂度仍是 O(m*n)，空间复杂度降到了 O(n)。代码短得让人怀疑是不是在写高数题。内层循环从左往右遍历是绝对且必须的，如果改成从右往左，你会发现 dp[j-1] 还是上一行的旧值，加出来的结果是错的。这一行循环方向就是很多面试题的隐藏考点，下面我会专门展开说。

3.3 还能再省一点吗：选小维度做滚动

滚动数组的空间是 O(n)，但 n 如果远大于 m，那其实浪费了不少空间。理论上你可以把网格转置一下，让列数等于 min(m, n)，从而把空间降到 O(min(m,n))。因为路径数跟网格方向的对称性有关，把行和列交换，答案不变。

实际写代码时，可以在开头加一个判断：

def uniquePaths(m: int, n: int) -> int: if m < n: m, n = n, m # 此时 n 是较小的一维 dp = [1] * n for i in range(1, m): for j in range(1, n): dp[j] += dp[j-1] return dp[-1]

这种优化在小数据量时看不出来，但对于超大规模网格（虽然这道题不会考到）或嵌入式环境下的内存限制，它是一种值得掌握的通用技巧。面试时主动做这一步，通常会是一个加分的亮点。

4. 组合数学解法：一条公式直接出答案

4.1 从“步数组合”角度看问题

现在我们把视角切换一下。既然机器人从左上角到右下角，总共需要走 m+n-2 步，其中恰好有 m-1 步是向下走的，剩下的 n-1 步是向右走的。那么不同的路径，其实就是从这 m+n-2 步中，选出哪 m-1 步向下走。这是个纯粹的排列组合问题。

所以答案就是：

ans = C(m+n-2, m-1)

举个例子，m=7、n=3，那么总步数是 7+3-2=8，其中向下 6 步，向右 2 步。答案是 C(8,2)=28，和题目示例给出的结果完全一致。m=3、n=2，总步数 3，向下 2 步，C(3,2)=3，也一致。

这个解法的精妙之处在于，它从根本上绕开了“逐格累加”的视角，直接把路径映射成“组合选择”。很多数学功底好的同学会在一分钟内靠这个公式出答案，而不需要建表、填表。但面试官问 DP 的时候，你直接甩出一个组合数公式，未必能完整展示 DP 能力，所以更好的策略是：先用 DP 思路分析，再提到“这题也可以转换成组合数学问题”，体现出思维的广度。

4.2 代码实现与溢出注意

Python 里可以直接用math.comb：

import math def uniquePaths(m: int, n: int) -> int: return math.comb(m + n - 2, m - 1)

但如果面试官让你手写组合数，你也要能写出来。常见实现是：

def uniquePaths(m: int, n: int) -> int: total = m + n - 2 k = m - 1 # 把 k 取最小值，减少计算量 k = min(k, total - k) res = 1 # 连乘除以 1..k for i in range(1, k + 1): res = res * (total - k + i) // i return res

这里有一个很长时间没接触算法的人容易忽略的坑：计算组合数时，最好是“边乘边除”而不是先算分子再算分母。如果先算分子 C 语言类型可能直接溢出，而且在 Python 以外的语言里，分子阶乘会非常快地超过 int 范围。虽然这道题 m、n 最大 100，C(198, 99) 在 C++ 的 64 位整数下已经轻度溢出了，所以 LeetCode 在 C++ 环境里通常能用 int 返回，是因为答案本身符合 int 范围，但中间过程的乘法要小心处理。

5. 常见错误与排查技巧实录

5.1 下标初始化：最容易被扣分的点

这是我在实际刷题和帮别人 review 代码时最常见的错误。很多人知道 dp[0][0] 要初始化为 1，或者知道第一行第一列要设置为 1，但经常把两者混在一起，写成类似这样的东西：

dp = [[0] * n for _ in range(m)] dp[0][0] = 1 for i in range(m): for j in range(n): if i == 0 and j > 0: dp[0][j] = dp[0][j-1] elif j == 0 and i > 0: dp[i][0] = dp[i-1][0] else: dp[i][j] = dp[i-1][j] + dp[i][j-1]

这种写法能得出正确答案，但逻辑绕了一个大弯。它隐含的意思其实是“第一行只能从左边来，第一列只能从上边来”。一旦你在某个格子初始化时不够仔细，第一行第一列中某几个格子变成 0，整个表就全错了。

更推荐的做法是直接想想：第一行的每个格子都只有一条路径吗？对，因为不能向上走，只能一路往右。那就可以初始化成 1，而不是从左边递推。第一列同理。这样后面循环从 i=1、j=1 开始，干净利落，完全规避了复杂的分支判断。

5.2 滚动数组循环方向的深坑

滚动数组写法里，内层循环必须从左往右：

for j in range(1, n): dp[j] += dp[j-1]

为什么不能从右往左？我们来模拟一下。假设上一行 dp = [1, 1, 1]，你要计算当前行。从左往右时，dp[1] 先变成 2，dp[2] 计算时用的是已经更新过的 dp[1]=2，得到 1+2=3，正确。如果从右往左，dp[2] 先计算，此时它看到的是 dp[1] 旧值 1，得到 1+1=2；接着 dp[1] 再更新成 2。只跑这一行，好像结果还算对，但等到下一行时，dp[2] 会被再更新，它依赖的 dp[1] 已经又是新值了，最终结果就会出现偏差。实际上每一行循环完成后，dp 数组代表的就是“当前行”的数据，下一行开始前它又当作“上一行”用。从右往左破坏了“dp[j-1] 必须优先更新为当前行新值”的前置条件，所以这是硬性错误。

如果你不确定方向，最简单的规避方法是回退到二维 DP 写法。面试现场稳比快更重要，能用二维 DP 把逻辑说清楚，再口头提一句“可以用滚动数组优化”，效果往往比写错方向的一维版本好得多。

5.3 结果类型与编码细节

LeetCode 原题在 C++ 里返回 int，m、n 最大 100，实际结果最大是 C(198,99)，约等于 2.27e58，这明明超过了 int 范围，但题目给的测试数据似乎都能放进 int。不过你在本地测试时，如果用 int 做组合数中间计算，大概率会炸。解决方式就是用 long long 或者 Python 这种高精度语言。如果你在 C++ 里做滚动 DP，dp 数组用 long long 最稳妥，最后返回时再转 int。

Python 不存在这个问题，但如果你在用 PyPy 刷题时见到奇怪的超时，别怀疑是精度问题，多半是你在循环里写了没必要的分支判断或者用列表生成式反复建表导致开销过大。一维滚动数组通常都够快。

5.4 边界条件自查清单

我建议你在提交前快速过一遍这几个用例：

• m=1, n=1：答案是 1，一个格子根本不用走。
• m=1, n=任意：答案是 1，只能一路向右。
• m=任意, n=1：答案是 1，只能一路向下。
• m=2, n=2：答案是 2，两条路径分别走“右、下”和“下、右”。
• m=3, n=3：答案是 6。

这几个用例全过，基本说明初始化和递推公式没写歪。

6. 题型进阶：一道经典题延伸出的 DP 方法论

6.1 变体一：有障碍物的不同路径

LeetCode 63 题目是“不同路径 II”，在网格中加入障碍物，值为 1 的格子不可通行。大部分解题思路和原题几乎一样，只是转移方程加一个条件：

if obstacleGrid[i][j] == 1: dp[i][j] = 0 else: dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始化的变化是重点：第一行遍历时，如果遇到障碍物，后面的所有格子都不可达，都要改成 0，而不是一直保持 1。第一列同理。这意味着你不能再无脑[[1]*n for _ in range(m)]初始化了。写这种变体时，我建议先画一遍带障碍物的 3×3 网格，把表格手算出来，再对照代码调试，效率极高。

6.2 变体二：最小路径和

LeetCode 64 是“最小路径和”，同样是 m×n 网格，每个格子上有数值，要求从左上到右下的路径中数字总和的最小值。状态定义变成 dp[i][j] 表示从左上角走到当前格子的最小花费，转移方程也随之变成：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

你会发现状态设计和转移推导的套路一模一样。很多 DP 题之间的差异，只是“在累计时用加法还是取 min/max”。这告诉我们，吃透一道中等题的核心推导过程，比盲目做十道同类型题更重要。

6.3 通用 DP 五步法

刷多了之后，我建议大家在做任何 DP 题时都固定走这五步：

1. 定义状态：dp[i][j] 表示什么？
2. 写转移方程：当前状态可以由哪些前置状态推导？
3. 初始化：边界条件是什么，哪个格子不需要递推就能确定？
4. 确定遍历顺序：行优先还是列优先？滚动数组方向是什么？
5. 用一个小例手工验证。

这道“不同路径”就是这五个步骤的标准模板。哪怕题目换到完全不同的场景，比如背包问题、股票买卖、编辑距离，核心推导流程也没变过。区别只是状态维度和转移逻辑变得复杂，但思考框架是通用的。

另外一个经验是：如果你在面试时遇到这道题，先不要急着写代码。花 10 秒想一想“这个题能不能用数学直接解”，顺便和面试官聊一句“这个思路其实和杨辉三角一致，也可以用组合数计算”，往往能让面试官对你的理解深度印象更好。但要立刻回到 DP 思路，因为面试官点名考 DP 的时候，组合数解法只能算补充，不能替代。

我在实际刷题过程中还有一个比较深刻的体会：很多同学看到 m、n 最大 100 就觉得怎么写都能过，于是草草把二维 DP 交上去。这本身没有错，但如果你能在草稿纸上手动算一遍 3×3 的 dp 表，再试着把二维表压缩成一维数组，你对 DP 状态的理解会直接上一个台阶。这种“慢下来推一遍”的功夫，远比为赶进度一口气刷 50 题更有回报。

最后分享一个小建议：做完这题之后，立刻把它和 63、64 连起来做一遍，你会发现三题之间只隔了一层窗户纸。能把三题放进同一个刷题日程里对比着做，比你单独搞懂一道题更有价值。DP 这东西，靠的是“状态视角”的反复训练，而不同路径正好是最适合入门的那扇门。