关于 LeetCode 62“不同路径”，说实话，这是我刷题路上第一道真正让我开窍的动态规划题。如果你刚接触 DP，或者刷了好几道还觉得状态转移方程是“背”出来的，那这篇内容值得你花十五分钟从头看到尾。我会从最核心的思路拆起，把 DP 的每一步推导、空间优化的两种写法、组合数学的解法和实际跑题时的踩坑全部串一遍，保证你看完能直接 AC，还能顺手应付后续的变体题。
1. 题目理解与状态定义：为什么这题是 DP 入门的最佳范本
1.1 先搞清楚题目在问什么
LeetCode 62 的题面很简洁：一个机器人位于 m x n 网格的左上角，每次只能向右或者向下移动一步，问到达右下角总共有多少条不同的路径。
注意几个关键条件：只能向右或者向下，意味着路径不会回头；不同路径指的是“走法的集合”不同，不是步数多少，因为从左上到右下，任何一条合法路径的步数都是固定的 m + n - 2 步。这个观察很重要，它直接指向了后面要讲的组合数解法。
我第一次做这道题时，脑子里冒出的第一个念头是“用 DFS 暴力搜索”，把每一条路径走完计数。这种思路对不对？对，但 m、n 到 100 的时候会超时。因为暴力搜索的时间复杂度是 O(2^(m+n))，指数爆炸。说白了，DFS 会把大量重复的子问题算了一遍又一遍。动态规划的核心价值就在这儿：把重复计算的结果存下来，用空间换时间。
1.2 dp 数组的含义，一句话说清
动态规划第一步永远是定义状态，也就是 dp[i][j] 到底代表什么。这题的状态定义非常直观：
dp[i][j] 表示从左上角 (0,0) 走到格子 (i,j) 总共有多少条不同路径。
那怎么求 dp[i][j]？机器人在到达某个格子之前，只可能从两个方向过来：要么从上方的格子向下走一步到达，要么从左侧的格子向右走一步到达。所以到达 (i,j) 的路径总数，天然等于到达上方格子的路径数加上到达左侧格子的路径数。
于是状态转移方程就出来了：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]这个方程不需要背，它是顺着题意“推”出来的。为什么能相加？因为到达上方格子和左侧格子的路径，走最后一步后都汇聚到 (i,j)，并且这两类走法不可能重复——一条路径的最后一步要么是向下，要么是向右，不存在同时满足的情况。这就是动态规划里最核心的“无后效性”和“子问题重叠”的直观体现。
1.3 边界条件：第一行和第一列为什么全是 1
光有转移方程还不够，必须明确 base case。左上角 (0,0) 到自身只有一条路径，就是什么都不走，所以 dp[0][0] = 1。那第一行 dp[0][j] 呢？因为第一行的格子只能从左边一路向右走过来，没有任何向下的机会，所以从 (0,0) 到第一行任意格子的路径数都是 1。同理，第一列 dp[i][0] 也都是 1——只能从上面一路走下来。
这个边界条件不需要硬记，你只需要想：“我能不能从上面/左边走到这个格子？”第一行上面没有格子，所以不可能是“上方路径数 + 左方路径数”，只能等于左边格子的路径数。从数学上就是把 i = 0 或 j = 0 时，转移方程中不存在的那一项忽略掉。
到这里，整道题的核心模型已经完整了：一个 m 行 n 列的二维表，从左到右、从上到下填充，每个格子等于上边加左边。这个模型一旦建立，后面无论是空间优化还是变体题，都是在它基础上做文章。
2. 从二维 DP 到存储优化：把空间省下来的两种有效姿势
2.1 基础二维写法，先确保 AC 再说优化
做算法题一条重要的原则：先写对，再写优。二维 DP 是最直观、最容易验证的思路，代码写出来长这样：
class Solution: def uniquePaths(self, m: int, n: int) -> int: # dp[i][j] 表示到达 (i,j) 的路径数 dp = [[1] * n for _ in range(m)] # 矩阵初始化后，第一行和第一列天然全为 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]这段代码的时间复杂度是 O(mn)，空间复杂度也是 O(mn)。LeetCode 的 m、n 上限是 100，所以这个版本提交完全没问题。我习惯把 dp 矩阵初始化为全 1，而不是全 0，是因为第一行和第一列本来就是 1，初始化成 1 省去单独赋值的步骤。这个写法有一点点“投机取巧”，但逻辑上没有问题。
从刷题输出的角度，能 AC 这道题，二维写法就达标了。但如果你面试的是要求比较高的岗位，面试官很可能追问一句“能不能优化空间”。这时候一维数组的思路就要上场。
2.2 一维滚动数组，把二维表压成一行
回到状态转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]。你会发现，算第 i 行的时候，只会用到第 i-1 行的数据，再往上的行就永远不再用了。既然每一行的计算只依赖上一行和当前行的左侧值，那完全可以用一个一维数组，一行一行地滚动更新。
关键在于更新顺序：从左到右更新 dp[j] 时，dp[j] 此刻存的还是上一行第 j 列的值（也就是原来的 dp[i-1][j]），而 dp[j-1] 在当前轮已经被更新成了本行第 j-1 列的值（也就是原来的 dp[i][j-1]）。两者相加，刚好就是新的 dp[j]。这是滚动数组的经典用法，也是空间优化的灵魂所在。
class Solution: def uniquePaths(self, m: int, n: int) -> int: # 一维数组，长度取列数 dp = [1] * n for i in range(1, m): for j in range(1, n): dp[j] = dp[j] + dp[j - 1] return dp[n - 1]这里有个容易绕晕的地方：为什么外层循环是行 i，内层循环是列 j，而不是反过来？因为状态转移方程里 dp[j] 依赖的是“上一行的同列值”和“当前行的左列值”。外层按行推进，内层从左到右推进，才能保证 dp[j] 读取到的仍然是上一行旧值、dp[j-1] 已经是本行新值。如果你把循环顺序反过来，dp[j] 可能在需要旧值之前就被覆盖掉了，结果直接出错。
这段代码时间复杂度和上面一样是 O(mn)，但空间从 O(mn) 压缩到了 O(n)。如果 m、n 中有一个特别大，这种优化立竿见影。比如 m=10000、n=2 的时候，二维数组要开 20000 个格子，一维数组只需要 2 个格子，差距非常明显。当然实际 LeetCode 的约束不会逼你到这个程度，但理解原理会让你遇到更复杂的题时游刃有余。
2.3 极限压缩：两个变量就够？数学上可行但没必要
还有人会提出进一步优化：既然 dp[j] 的更新只依赖 dp[j] 和 dp[j-1]，那是不是可以用两个变量滚动？从纯理论推导是可行的——本质上每一行每一列的计算只需要保留“上一行的某个格子”和“当前行的前一个格子”。但在二维路径问题里，这种两个变量的写法的可读性会大幅下降，而且循环里还要手动维护多个临时变量，非常容易出错。
我个人不太推荐在面试或日常题解中写这种极限版本。原因很简单：一维数组版本在可读性和空间效率之间达到了最佳平衡——它仍然能清楚表达“逐行更新”的语义，也好向面试官解释。空间优化做到 O(n) 已经是这类题的常态要求，继续压到 O(1) 属于炫技，边际收益不大。真到了内存极度受限的场景，直接换组合数解法不是更干净吗？
3. 用组合数学彻底看透路径本质：DP 之外的线性级解法
3.1 所有路径本质上是“选择问题”
如果只看 DP 解法，你可能会误以为动态规划是解这道题的唯一正解。其实还有一个更接近问题本质的视角——排列组合。
机器人从左上角到右下角，总共需要走 (m - 1) + (n - 1) = m + n - 2 步。其中向下走 m - 1 步，向右走 n - 1 步。任何一种走法，本质上就是在 m + n - 2 个位置里，选出 m - 1 个位置用来“向下”，剩下的位置自然就是“向右”。
所以不同路径的总数就是组合数 C(m + n - 2, m - 1)，也就是在 m+n-2 步中选 m-1 步向下走的方法数。
举个例子，m=3、n=7 的网格，总共要走 3-1+7-1=8 步，需要选 2 步向下、6 步向右。那 C(8, 2) = 28，答案就是 28。这个结果和 DP 算出来一模一样，但耗时是 O(m) 而不是 O(m*n)。
3.2 为什么 DP 和组合数能得到同一个答案
很多人刷完题会有个困惑：两种解法看起来完全不同，怎么答案一样的？从数学上讲，组合数直接计算的是“选择向下位置”的总数；而 DP 是在逐格累加所有能汇聚到当前格子的选择方案数。DP 的本质其实就是组合数的递推计算：C(m+n-2, m-1) 可以按行和列拆解为无数次相邻格子的加和，也就是杨辉三角的构建过程。
你甚至可以这么理解：二维 dp 表本身就是杨辉三角的一部分，只不过角度发生了偏移。第一行和第一列是杨辉三角的边界 1，内部每个格子是左上两个值的和，这和杨辉三角的计算方式一模一样。这个发现会加深你对动态规划“为什么记忆化加法能算组合数”的直观感受。
3.3 组合数的代码实现与溢出陷阱
组合数写起来并不复杂，但直接算阶乘再相除会非常容易溢出。m、n 在 100 时 C(198, 99) 是一个超大数，Python 的大整数能扛住，但 C++/Java 的 long long 早就爆了。所以更稳妥的写法是边乘边除，也就是按公式展开时约分处理：
class Solution: def uniquePaths(self, m: int, n: int) -> int: # 总共需要移动的步数 total = m + n - 2 # 取较小的那个作为 k，减少循环次数 k = min(m - 1, n - 1) result = 1 for i in range(1, k + 1): result = result * (total - k + i) // i return result这段代码利用了组合数的递推公式：C(n, k) = C(n, k-1) * (n - k + 1) / k。用 for 循环从 1 到 k，每一步做一次乘法和一次除法。由于每一步除的都是当前 i，并且乘法部分 (total - k + i) 保证了中间结果始终能整除，所以结果是精确的整数。
注意一个细节：我在代码里取了 k = min(m - 1, n - 1)，是为了让循环次数更少。C(n, k) 和 C(n, n-k) 相等，选小的那个 k 算起来更快。这是组合数计算的一个常用优化，虽然在这个题的数据规模下收益有限，但好习惯值得养成。
用组合数法解题时，时间复杂的只有 O(min(m, n))，比 DP 快一个数量级。不过它的问题在于思路不直观——如果你一上来就想着排列组合，可能很难向别人解释清楚为什么这样算是对的。所以我一般建议：先掌握 DP，再理解组合数。两条腿走路，刷题面试都稳。
4. 实操录：从读题到提交的全过程复盘
4.1 我的第一版代码和耗时分析
这道题我第一次提交用的是最经典的二维 DP，写到 AC 的过程中没有调代码，但从读题到完全推导出状态方程，大概花了几分钟。很多同学觉得 DP 难，其实难的是“不敢定义一个状态”。突破口就在题目的条件里：移动方向只有向下和向右，那到达一个格子的来源就明确规定了两种。只要把这层想明白，dp[i][j] = dp[i-1][j] + dp[i][j-1] 就是水到渠成。
当时我用 Python 提交，耗时大约 24ms，击败了接近六成的提交，内存占用 13MB 左右。这个成绩在今天看来并不亮眼——因为 Python 的解法中，一维滚动数组的版本耗时更低，大概 16ms 左右。如果你追求排名更靠前，可以试试一维做法。但说实话，击败率这种指标不用太较真，重要的是思路清晰、能应对追问。我面试时被问到这题，面试官关心的根本不是击败率，而是我对空间优化和组合数推导的理解深度。
4.2 一个容易被忽略的“输入方向”问题
LeetCode 62 有个容易让人踩坑的细节：函数签名 uniquePaths(m, n) 里，m 代表行数，n 代表列数。但很多人在阅读题解时会看到别人写 f(i, j) 或者用 width、height 来表示网格规格，不同文章里可能正好相反。
这个差异如果不注意，在你把代码从 Python 抄到 Java 或者从一份题解换到另一份时，可能产生困惑：为什么循环里 i 是从 1 到 m，j 是从 1 到 n？为什么返回的是 dp[m-1][n-1] 而不是 dp[n-1][m-1]？只要搞懂 m、n 在题目定义中的角色，并且确保你遍历的是行和列而不是僵记下标顺序，这类问题就不会误导你。
我遇到过一些初学者，把一维数组的长度定义成 m 而不是 n，导致索引越界或者结果错误。实际上，一维数组代表的是“当前行的各个列”，所以它的长度应该是 n。如果你把数组长度设为 m，再把外层循环跑 n 次，虽然逻辑上对称，但代码的语义就乱了。写代码时定义清楚变量含义，比码字速度更重要。
4.3 我用这道题总结出的 10 个 DP 快手要点
刷完这道题后，我把自己的思路沉淀成了一张“DP 快速检查清单”，分享出来给大家参考：
- 题目问的是不是最优值、方案数、可行性？如果是，优先考虑 DP。
- 看状态能不能用一个或几个参数完全描述当前“阶段”。这里就是 (i, j)。
- 找“子问题重叠”：大格子的路径数能不能拆成更小格子的路径数之和？
- 从一步转移出发，想象机器人最后一步从哪里来，状态转移方程就写出来了。
- 边界条件永远从“无法转移”的状态开始找，比如第一行和第一列。
- 计算顺序要满足依赖关系——算 dp[i][j] 前，dp[i-1][j] 和 dp[i][j-1] 必须已经算完。
- 能用滚动数组就尝试滚动数组，观察当前行是否只依赖上一行。
- 复杂度分析别偷懒：时间、空间都写上，面试官很在意这步。
- 把 dp 表打印出来，对照手工推算的答案，能快速发现状态定义错在哪。
- 变换视角：如果题目本质是组合选择，数学解法有时比 DP 更好写。
这十条并不是 LeetCode 62 独有，后续你刷 LeetCode 64（最小路径和）、LeetCode 63（不同路径 II）、LeetCode 120（三角形最小路径和）时都可以直接复用。
5. 常见问题与排查技巧实录
5.1 为什么我的 DFS 超时，DP 却很快？
这是刚入门 DP 时最常问的问题。DFS 本质是递归枚举所有路径，而路径总数是组合数规模，当 m、n 增大时路径数呈指数级别膨胀。DP 则把每个子问题的解保存下来，每个格子只计算一次。因此 DFS 的复杂度是指数级，DP 是多项式级（本例是 O(m*n)，组合数学是更低）。
很多初学者会把“递归”和“DP”混为一谈。其实记忆化搜索（递归 + memo）也是 DP 的一种实现形式，只是为了递归栈开销，在深度大的场景下不如迭代版稳。LeetCode 62 如果用 Python 递归 + memo，一般也能过，但迭代版空间更小、执行更稳。我倾向直接推荐迭代。
5.2 组合数解法会不会溢出？怎么预防？
在 Python 里大整数是无限精度的，所以唯一需要考虑的是效率。但在 C++、Java 等语言中，m、n 上限 100 时，C(198, 99) 远超过 32 位整型范围，需要 64 位乃至更长的数据类型。更稳的方案是边乘边除，把中间结果压到最小。如果题目再把范围放大，你可能还需要用取模大数的模板，那就是另一类进阶题了。
如果你只是刷 LeetCode 的 Python 版本，基本不用担心溢出。但面试中面试官可能会故意问“如果 m、n 是 10^9 怎么办？”这种问题时，你要意识到 DP 已经没法做了，必须用组合数加取模处理——当然 LeetCode 62 的连乘结果也不可能在 10^9 规模下承载，所以碰到这类追问，更多是考察你对复杂度本质的理解。
5.3 为什么我的一维数组结果总是偏小？
一维数组版本最常见的 bug 是没把 dp[0] 初始化为 1，或者在更新时把 dp[j] 和 dp[j-1] 的加和顺序写反。另一个常见的错误是内层循环从 j = 0 开始，把 dp[0] 又算了一遍。dp[0] 永远是边界，保持 1 就可以。我调试过很多次发现，只要把内层循环从 j = 1 开始执行，结果就正常；从 j = 0 开始，d[0] 会变成 2，结果一路错到底。
还有一个隐蔽问题是直接复制二维 DP 的初始化思路，把一维数组初始化成全 0。这样第一行全变 0，最后答案自然为 0。所以一维数组初始化要显式写成 [1] * n，这不是写不写的问题，而是变量语义决定的。
5.4 这题的变体我该怎么准备？
LeetCode 62 的“家族”很庞大，最典型的就是 LeetCode 63（不同路径 II，网格里有障碍物）和 LeetCode 64（最小路径和，每个格子有权重）。63 的思路是在 DP 转移时增加判断，遇到障碍物直接置 0；64 是把求和变成取最小，同时注意边界格子的累加方式要相应调整。如果你把 62 的推导过程吃透，这两道题都是小改动。
也常有人问“能不能用 BFS 解这题”。理论上网格图的最短路径类题目可以用 BFS，但这里要计数所有路径，BFS 会访问大量重复状态，记忆化去重的话本质上又回到 DP。所以 BFS 不是这道题的最优思路，但理解这个联系有助于你在更复杂的图上搜索类问题中做出合理选择。
6. 刷完这道题之后，我留下的几个思考习惯
6.1 一道题的价值不在 AC，而在建立“迁移模板”
LeetCode 62 是一个“极简状态 DP”的典型模板。状态 = 位置，转移 = 相邻方向。你可以在自己号的笔记里把这类二维路径 DP 单独归为一类，记录状态定义、转移方程、边界处理。我自己的做法是每个模板类别写一个通用代码骨架，后续不同题只要修改状态含义和转移规则即可。比如障碍物版本就是“遇到障碍物跳过”，权重版本就是“加权重取小”。这种模板化思维，刷题效率会翻倍。
6.2 不必一开始就追求最优解，但一定要理解所有解法的“为什么”
我见过很多刷题者只背一维数组版本，因为代码短。但真要他在白板上解释“为什么 dp[j] 加的是旧值”，他就会卡住。追问最后一步的时候，他对“状态更新时机”的理解就露馅了。所以我的建议是：先手写二维版本，再手动模拟一遍 dp 表的填充过程，最后才看一维优化。这个过程看似多花十分钟，实际上能帮你绕开未来无数个 DP 类问题的空间优化困惑。
6.3 最后分享一个小技巧：用“手工小矩阵”核验代码
无论你写了哪种解法，提交前花 10 秒手工验证一个 m=3、n=3 的用例。答案应该是 6。你可以快速画出 3x3 的格子，填出 dp 表，确认代码输出与自己手算一致。这个小习惯几乎不花时间，却能在考场上和刷题时帮你避免大量低级失误。甚至面试官看着你花 10 秒手算验证，也会觉得你的工程素养很好——不是写完就跑，而是有验证闭环的思维。
我现在遇到新 DP 题，还会习惯性地先问自己：这个问题本质上是在选什么？如果是选择组合，那组合数学是更快的答案；如果带有障碍或权重，那 DP 才是更通用的工具。这种“双视角”思考，让我在 LeetCode 62 之后的很多题里都省下了大量试错时间。希望这篇复盘能帮你把这道题的底层逻辑彻底钉进脑子里，往后遇到“不同路径”系列，直接形成条件反射。
