好的，我们这次来详细学习 LeetCode 第 62 题「不同路径」。

1. 题目描述

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start”）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角到右下角一共有 3 条路径：
1. 右 -> 下
2. 下 -> 右
3. 右 -> 下

约束条件：

• 1 <= m, n <= 100

2. 思路分析

2.1 理解问题

• 网格大小：m 行 n 列。
• 从 (0, 0) 到 (m-1, n-1)。
• 只能向右或向下。
• 求路径总数。

2.2 初步思考

如果 m = 1 或 n = 1，只有一条路径（直走）。
对于一般情况，到达 (i, j) 的路径数 = 从 (i-1, j) 下来的路径数 + 从 (i, j-1) 右移过来的路径数。
这实际上是一个动态规划的经典问题。

3. 动态规划解法

3.1 定义状态

设 dp[i][j] 表示从 (0, 0) 走到 (i, j) 的不同路径数量。

3.2 状态转移方程

• 如果 i > 0 且 j > 0：dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 如果 i = 0 且 j > 0：dp[0][j] = dp[0][j-1]（第一行，只能从左边来）
• 如果 j = 0 且 i > 0：dp[i][0] = dp[i-1][0]（第一列，只能从上边来）
• dp[0][0] = 1（起点）

3.3 初始化

dp[0][0] = 1，然后按行或按列递推。

4. 详细推导（示例 m=3, n=2）

我们手动算一下 m=3, n=2 的情况。

网格坐标：

(0,0)  (0,1)
(1,0)  (1,1)
(2,0)  (2,1)

初始化：

• dp[0][0] = 1

第一行：

• dp[0][1] = dp[0][0] = 1

第一列：

• dp[1][0] = dp[0][0] = 1
• dp[2][0] = dp[1][0] = 1

中间位置：

• dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
• dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3

结果： dp[2][1] = 3，与示例一致。

5. 代码实现（Python）

def uniquePaths(m: int, n: int) -> int:
    # 创建 m x n 的 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]

6. 优化空间复杂度

当前空间复杂度 O(m×n)，但我们可以优化到 O(n)：

因为 dp[i][j] 只依赖于上一行 dp[i-1][j] 和当前行左边的 dp[i][j-1]，我们可以只保留一行。

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]（还没被覆盖） + 当前行左边的 dp[j-1]
            dp[j] = dp[j] + dp[j-1]
    
    return dp[n-1]

7. 数学组合方法（扩展思路）

从 (0,0) 到 (m-1, n-1) 一共需要移动 (m-1) + (n-1) = m+n-2 步，其中向下 m-1 步，向右 n-1 步。
路径总数等于从 m+n-2 步中选出 m-1 步作为向下的组合数：

\[C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)! (n-1)!} \]

Python 实现：

import math

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

8. 总结

• 核心思路：动态规划，dp[i][j] = dp[i-1][j] + dp[i][j-1]。
• 边界处理：第一行和第一列都是 1。
• 空间优化：用一维数组代替二维，空间 O(n)。
• 数学方法：组合数公式直接求解。

这样循序渐进地理解，你应该能掌握这个题目的解法了。需要我进一步解释哪一部分吗？