62. 不同路径（Unique Paths）
难度：中等 | 主题：DP、组合数学
题目
m x n 网格，机器人从左上角走到右下角，只能向右或向下，求不同路径数。
示例
输入：m = 3, n = 7
输出：28
思路
先讲个故事：迷宫导航
你站在一个网格迷宫左上角，手机导航说只能往右或往下走。走到右下角有多少种走法？
一开始你可能会想：每次到十字路口有 2 种选择…但等等，到同一个格子可能从左边来、也可能从上边来——路径在这里汇合了。
这不是选择题，是路径计数：每个格子记下”从起点到这儿有多少种走法”，然后往后传。
引导式推导：动手填表
第 1 步（边界条件）
第一行：只能一直往右 → 只有 1 条路径
第一列：只能一直往下 → 只有 1 条路径
第 2 步（中间格子）
要到达 (i, j)，上一步只可能来自：
-
上方
(i-1, j)→ 往下走一步 -
左方
(i, j-1)→ 往右走一步
这两种情况互斥且覆盖所有可能，所以路径数相加：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
第 3 步（推广）
3×3 网格填一圈：
flowchart TD subgraph grid["3×3 网格填表"] c11["1"] --> c12["1"] c12 --> c13["1"] c11 --> c21["1"] c21 --> c31["1"] c12 --> c22["2<br/>(上1+左1)"] c13 --> c23["3<br/>(上1+左2)"] c21 --> c22 c22 --> c23 c22 --> c32["3<br/>(上2+左1)"] c31 --> c32 c23 --> c33["6<br/>(上3+左3)"] c32 --> c33 end style c33 fill:#ffd700
四层递进：从暴力到最优
graph LR A["暴力递归<br/>O(2^(m+n))"] -->|缓存剪枝| B["记忆化搜索<br/>O(m×n) 空间"] B -->|递归改递推| C["二维 DP<br/>O(m×n) 空间"] C -->|滚动数组| D["一维 DP<br/>O(n) 空间"] D -->|组合数| E["C(m+n-2, m-1)<br/>O(min(m,n))"]
暴力递归：f(i,j) = f(i-1,j) + f(i,j-1)，但大量重复计算。
记忆化搜索：@lru_cache 搞定，时间 O(m×n) 但递归栈有开销。
自底向上 DP：从 (0,0) 填表到 (m-1,n-1)，二维数组。
滚动变量：观察 dp[i][j] 只依赖当前行左边 dp[i][j-1] 和上一行同列 dp[i-1][j]。用一维数组：
dp[j] += dp[j-1]
dp[j] 更新前是上一行的值（上方），dp[j-1] 已被当前行更新（左方）。为什么 j 从左到右？因为需要 dp[j-1] 是当前行的新值。
数学组合数：总共 (m-1)+(n-1) 步，选 (m-1) 步向下，其余向右。C(m+n-2, m-1)，math.comb 一行搞定。
代码
def uniquePaths(self, m, n):
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[n-1]
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| DP 时间 | O(m × n) | 双重循环遍历所有格子 |
| DP 空间 | O(n) | 一维数组滚动更新 |
| 组合数时间 | O(min(m,n)) | math.comb 计算一次 |
| 组合数空间 | O(1) | 不耗额外空间 |
实战考量
频率分析
出现在：几乎所有公司一面必考 DP 题之一。约 50% 的 AI Agent 常从这道题开始 DP 轮——简单直观，方便追问优化。字节/美团/阿里一面的 DP 热身首选。
延伸思考
Q：数学组合公式怎么推导？
A：总共 (m-1)+(n-1) 步移动，选 (m-1) 步向下，其余向右。C(m+n-2, m-1) = C(m+n-2, n-1)。
Q：为什么 dp[j] += dp[j-1] 能工作？
A：dp[j] 保留上一行的值（从上方来），dp[j-1] 是当前行刚更新的值（从左方来）。利用了更新顺序复用值。
Q：有障碍物（63 题）呢？
A：障碍物处 dp[j] = 0。第一行/列遇障碍后后续全 0。初始化需要特殊处理。
Q：组合数会溢出吗？
A：Python 整数无上限。C++/Java 需要 long long 或 BigInteger。用组合数学要提溢出风险。
Q：m,n 很大（如 10⁵）怎么办？
A：DP 的 O(mn) 会超时，用组合数学 O(min(m,n))。
易错点
-
dp初始化为全 1（第一行全是 1） -
j 从 1 开始（第一列永远是 1，不更新）
-
dp[j] += dp[j-1]依赖dp[j-1]是当前行最新值（j 从左到右遍历正确） -
n=1 或 m=1 时循环不执行，直接返回 1
生活类比
迷宫导航 → DP 填表 → 滚动数组
每个格子都记着”从起点到这儿有多少条路”——就像地铁站人流计数器，每个站累加前一个站的人数。
滚动数组就是只带一行计数器走完迷宫，走完一行丢掉上一行。
三个字：累加传。
相关题目
→ 返回题单：LeetCode学习路线图 > 十三、动态规划
速记卡（面试闪卡）
Q1：一句话讲清「62. 不同路径（Unique Paths）」到底是什么？
A：m×n 网格，机器人从左上角只能向右或向下走到右下角，求不同路径数。本质是网格上的路径计数。
Q2：题目与迷宫导航 —— 怎么理解？
A：像迷宫导航——到同一个格子可能从左边来、也可能从上边来，路径在这里「汇合」了。这不是二选一的选择题，而是路径计数：每个格子记下「从起点到这儿有几种走法」，然后往后传，像地铁站人流计数器。
Q3：思路与递推 —— 怎么理解？
A：边界上第一行、第一列只能一路直走，全是 1。中间格子到达方式 = 从上方来 + 从左方来，二者互斥且覆盖所有可能，所以 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
Q4：优化与组合 —— 怎么理解？
A：观察到 dp[i][j] 只依赖当前行左边和上一行同列，用一维 dp[j] += dp[j-1]（j 从左到右复用）；更直接地，总共走 (m-1)+(n-1) 步选 (m-1) 步向下，组合数 C(m+n-2, m-1) 一行搞定，O(min(m,n))。
Q5：复杂度与障碍 —— 怎么理解？
A：DP 时间 O(m×n)、空间 O(n)；组合数空间 O(1) 但 C++/Java 要注意溢出（用 long long）。有障碍的 63 题只需把障碍处 dp[j]=0，第一行/列遇障碍后后续全 0。
Q6：核心速记主线有哪些？
A：题目、边界全 1、递推求和、滚动数组、组合数、障碍变体。
口诀
A：不同路径右和下，边界全 1 中间加；
滚动一维复用好，组合数法一行拿。