LeetCode 62. 不同路径：把动态规划搬到网格上

不同路径（LeetCode 62，Medium）是动态规划的「网格第一课」：m×n 的网格，机器人从左上角走到右下角，每步只能向右或向下，问有多少条不同路径。它是把一维 DP（本库《爬楼梯》《打家劫舍》）搬到二维的第一步——转移方程的形状几乎没变，变的只是「状态住进了格子」。本篇讲清网格 DP 的通用框架、空间优化、以及这道题藏着的组合数学惊喜。

网格 DP 的通用框架：状态、转移、遍历顺序

状态：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。遍历顺序：因为转移只依赖「上方与左方」，按行从左到右遍历即可保证依赖就绪。答案 dp[m-1][n-1]。时间空间 O(m×n)。网格 DP 的通用性：这个「状态=格子、转移=来自相邻格子」的框架，直接通吃一族经典题——最小路径和（路径数换成路径上的最小和）、带障碍物的不同路径 II（障碍格 dp 置 0）、以及更复杂的网格问题（本库语境里的「背包在网格上」变体）——学会这个框架，网格类的 DP 就是一套模板换初始化与转移细节。

空间优化：滚动数组（一维化）

转移只依赖「上一行的同列」与「本行的左列」——整张表其实只需要一行。滚动写法：用一维数组 dp[j] 表示「当前行第 j 列」，遍历每行时，dp[j]（还没更新）恰好是上一行的值，dp[j-1]（刚更新）是本行左边的值——转移写成 dp[j] += dp[j-1]：

def unique_paths(m: int, n: int) -> int:
    dp = [1] * n                       # 第一行全为 1
    for _ 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)。滚动数组的通用技巧：判断「能不能一维化」的检验只有一条——转移是否只依赖「上一行」与「本行已更新的部分」；依赖「上上行」就要保留两行，依赖「右下角」的遍历方向要倒过来（本库《背包问题》的滚动优化正是同款技巧的一维背包形态）。这个技巧的命名值得记住：滚动数组不是省空间的魔法，是「发现依赖半径小于表宽」之后的自然结果——先看清依赖，再谈优化。

惊喜：这就是组合数学

最后揭晓这道题的「另一副面孔」：机器人总共要走 m+n-2 步，其中 m-1 步向下、n-1 步向右——一条路径的本质，是在 m+n-2 个位置里选出 m-1 个「向下」的位置。路径数就是组合数：C(m+n-2, m-1)。用 Python 验证：math.comb(m + n - 2, m - 1) 一行搞定，时间 O(min(m,n))、空间 O(1)。这个视角的两层价值：其一，性能上完胜 DP（面试的加分答案：「DP 能做，但这题其实是组合数」——一句展示你对问题结构理解深度的话）；其二，它揭示了 DP 的一个本质：很多「计数型 DP」的转移方程，其实是组合恒等式的递推形式——C(n,k) = C(n-1,k-1) + C(n-1,k) 与本篇的 dp[i][j] = dp[i-1][j] + dp[i][j-1] 是同一个式子换了坐标（杨辉三角就是这张网格）。「DP 与组合数学的这层同构」是计数问题的通用视角：写出 DP 之后，值得多问一句「这个递推有没有闭式解」。

与「带障碍物」续作的衔接 + 滚动方向的小实验

62 的框架直接延伸到带障碍物的续作（LeetCode 63）：障碍格的路径数为 0，转移前加一个判断——if obstacle: dp[j] = 0 else dp[j] += dp[j-1]。滚动数组的细节在障碍物版本里有一个著名的坑：起点本身是障碍（dp[0] 应为 0）与「障碍之后的本行首个可达格」——滚动后 dp[0] 每行的重置必须跟随障碍状态（第一列的路径数逐行继承：没有障碍则保持 1，遇到障碍后归零且之后恒零）。滚动方向的小实验：把内层循环的方向从左到右反转为从右到左会怎样？dp[j] += dp[j-1] 中 dp[j-1] 变成「上一行的左格」（未更新）——恰好还是正确的！因为本问题的转移只依赖「上一行」与「本行左边」，两种方向都满足依赖就绪——但这个巧合不可泛化（依赖「本行右边」的反向转移就需要正序遍历），遍历方向的确定永远从「依赖分析」出发，而不是从「试验」出发。最后一个验证：组合数公式的交叉核对——m=3, n=7 时 C(8,2)=28 ✓ 与 DP 一致；m=100, n=100 时组合数是 30 位的大数，Python 的整数无溢出之忧（其他语言要用模运算版本——LeetCode 变体要求 mod 1e9+7，那是另一个工程细节）。

DP 表的可视化：不同路径就是杨辉三角的旋转

不同路径的 DP 表，画出来有一个惊人的发现：它就是杨辉三角的平移变形。3×7 的 DP 表逐行写出：第一行全是 1；第二行是 1, 2, 3, 4, 5, 6, 7；第三行是 1, 3, 6, 10, 15, 21, 28——每一行的相邻关系恰好是杨辉三角的递推（左上 + 上）。把网格逆时针旋转 45 度，这张表就是杨辉三角的截取——「向右或向下走的路径数」与「杨辉三角的生成规则」是同一个组合恒等式的两种呈现。这个可视化的三个收获：其一，DP 表的每一行是前一行的前缀和（第二行 = 第一行的前缀和；第三行 = 第二行的前缀和——「前缀和套前缀和」的嵌套结构）；其二，组合数的递推与路径数同源（C(n,k) 的杨辉递推就是路径数的转移——本篇正文的组合数惊喜在此有了「为什么」）；其三，可视化是检查 DP 正确性的廉价手段（表画出来，用肉眼看对称性与单调性是否合理——异常的表值立刻暴露转移方程的笔误）。给学习者的建议：每学一个新的 DP，把小规模（3×5）的表手画一遍——画表的三分钟，是最便宜的调试。

网格 DP 的变体族谱：最小路径和、三角形、下降路径

不同路径的框架通吃网格族的三道变体，框架不变只换「聚合函数」。最小路径和（LeetCode 64）：路径数换成路径上的最小数字和——转移从「相加计数」变为「取上左较小者加当前格」——聚合函数从计数变为 min 加权。三角形（LeetCode 120）：网格变成三角形（每行少一个格），转移来自「上一行的同列与左列」——滚动数组时从右往左遍历（三角形依赖「上一行的两个位置」，正序遍历会覆盖还没用的值）。下降路径最小和（LeetCode 931）：转移来自「上一行的左/中/右」三格取 min——方向更多，框架不变。三道变体的共同点：状态住在格子里、转移来自相邻格子、按依赖方向遍历——「聚合函数」（计数/求和/取 min/max）与「邻接定义」（两个来源/三个来源）是仅有的自由度。网格族的通用性一句话：学会了 62 的框架，网格 DP 的家族就是一套模板的换肤。

从组合数看 DP 与数学的「交叉验证」

不同路径的组合数惊喜（本篇正文）揭示了一个方法论问题：当你同时知道 DP 解法与组合数闭式公式时，两者可以交叉验证——DP 的结果与 C(m+n-2, m-1) 不一致时，必有一个是错的。这种交叉检验的深层价值在于：DP 错了说明状态转移建模有误（回溯检查状态定义）；公式错了说明组合模型的理解有误（回溯检查组合论证）。两条独立路径的错误定位互相隔离，调试效率倍增。这个方法在工程里的对应物：同一功能的两套实现（精确但慢、近似但快）在抽样数据上交叉验证。算法学习教的不只是算法，是用独立路径验证结论的思维方式——这是本篇最深远的一课。

从组合数看 DP 与数学的交叉验证

不同路径的组合数惊喜揭示了一个方法论问题：当你同时知道 DP 解法与组合数闭式公式时，两者可以交叉验证——DP 的结果与 C(m+n-2, m-1) 不一致时，必有一个是错的。这种交叉检验的深层价值在于：DP 错了说明状态转移建模有误；公式错了说明组合模型的理解有误。两条独立路径的错误定位互相隔离，调试效率倍增。这个方法在工程里的对应物：同一功能的两套实现（精确但慢、近似但快）在抽样数据上交叉验证。算法学习教的不只是算法，是用独立路径验证结论的思维方式——这是本篇最深远的一课。

组合数的另一个视角：路径数=杨辉三角的切片

62 题的 DP 表画出来有一个惊人的发现：它就是杨辉三角的旋转变形。3×7 的 DP 表逐行写出：第一行全是 1；第二行是 1,2,3,4,5,6,7；第三行是 1,3,6,10,15,21,28——每一行的相邻关系恰好是杨辉三角的递推。把网格旋转 45 度，这张表就是杨辉三角的截取。这个可视化的收获：DP 表的每一行是前一行的前缀和（前缀和套前缀和的嵌套结构）；组合数的递推与路径数同源；可视化是检查 DP 正确性的廉价手段（表画出来用肉眼看对称性与单调性是否合理）。给学习者的建议：每学一个新的 DP，把小规模（3×5）的表手画一遍——画表的三分钟是最便宜的调试。

小结

这篇收成四条：网格 DP 通用框架——状态住格子、转移来自上方与左方、按行遍历，一套模板通吃路径族问题；滚动数组把 O(m×n) 压到 O(n)，检验标准是「转移依赖半径小于表宽」；这道题的惊喜是组合数——路径的本质是「在 m+n-2 步中选 m-1 步向下」，C(m+n-2, m-1) 一行搞定且揭示了 DP 与组合恒等式的同构；DP 之后多问一句「有没有闭式解」，是计数问题的进阶习惯。网格系列的下一课是「带障碍物的不同路径」——框架不变，初始化与转移各加一个 if。

参考资料

• LeetCode 62. Unique Paths —— 题目与官方题解；LeetCode 63（带障碍物）为续作
• 本库前篇：《LeetCode 70. 爬楼梯》《LeetCode 198. 打家劫舍》—— 一维 DP 的前置
• 杨辉三角与组合恒等式（Pascal's rule）—— DP 与组合数学同构的数学背景