我来给你讲解 LeetCode 第 62 题：不同路径（Unique Paths）。
题目描述
一个机器人位于一个 m x n 网格的左上角（起点），机器人每次只能向下或者向右移动一步。机器人试图到达网格的右下角（终点）。
问总共有多少条不同的路径？
示例
- 输入：
m = 3,n = 7 - 输出：
28
约束
1 <= m, n <= 100
思路分析
1. 问题理解
这是一个经典的计数型动态规划问题。
机器人从 (0,0) 到 (m-1, n-1)，每次只能向右或向下，意味着：
- 到达某个格子
(i, j)的路径数，等于从它左边来的路径数加上从它上边来的路径数。
2. 定义状态
设 dp[i][j] 表示从起点 (0,0) 走到 (i,j) 的不同路径数。
3. 状态转移方程
- 如果
i > 0且j > 0：
dp[i][j] = dp[i-1][j] + dp[i][j-1] - 如果
i = 0或j = 0，即在网格的第一行或第一列，那么只有一条路径（一直向右或一直向下），所以：
dp[0][j] = 1（对任意 j）
dp[i][0] = 1（对任意 i）
4. 初始条件
dp[0][0] = 1（起点到起点只有一条路径：不动）
详细推导（以 m=3, n=3 为例）
网格如下（3x3）：
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
初始化：
- 第一行全部为 1：
dp[0][0]=1, dp[0][1]=1, dp[0][2]=1 - 第一列全部为 1：
dp[1][0]=1, dp[2][0]=1
计算过程：
-
dp[1][1]：可以从(0,1)向下，或从(1,0)向右：
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2 -
dp[1][2]：可以从(0,2)向下，或从(1,1)向右：
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3 -
dp[2][1]：可以从(1,1)向下，或从(2,0)向右：
dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3 -
dp[2][2]：可以从(1,2)向下，或从(2,1)向右：
dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6
所以最终结果是 6。
代码实现（Python）
def uniquePaths(m: int, n: int) -> int:
# 初始化 dp 表，全为 1（因为第一行和第一列都是 1）
dp = [[1] * n for _ in range(m)]
# 从 (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]
复杂度分析
- 时间复杂度：O(m × n)，需要填充整个二维 DP 表。
- 空间复杂度：O(m × n)，可以优化到 O(n)（只保存一行）。
优化空间复杂度
因为计算 dp[i][j] 时只依赖于当前行前一列 dp[i][j-1] 和上一行同一列 dp[i-1][j]，所以可以用一维数组（长度为 n）来存储：
def uniquePaths(m: int, n: int) -> int:
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] 是上一行的值（上方），dp[j-1] 是当前行左边的值（左方）
return dp[n-1]
组合数学解法（进阶）
这个问题等价于：从起点到终点，一共需要移动 m-1 次向下，n-1 次向右，总共 m+n-2 步。
不同路径数等于从 m+n-2 步中选择 m-1 步作为向下的步数（其余向右）：
\[\text{路径数} = C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)!(n-1)!} \]
对于 m=3, n=3：
\[C(4, 2) = \frac{4!}{2! \cdot 2!} = 6 \]
这种方法时间复杂度 O(min(m, n))，空间复杂度 O(1)。
这样，我们就从基础思路到优化，再到数学方法，完整讲解了“不同路径”问题。