我来给你讲解 LeetCode 第 62 题「不同路径」。

题目描述

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

示例
m = 3, n = 7，输出 28。

解题思路

1. 问题分析

• 从 (0,0) 到 (m-1, n-1)，只能向右或向下。
• 路径数量与网格大小有关，可以分解为子问题。
• 到达 (i,j) 的路径数 = 从 (i-1,j) 下来的路径数 + 从 (i,j-1) 向右来的路径数。

2. 动态规划定义

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

状态转移方程：

\[dp[i][j] = dp[i-1][j] + dp[i][j-1] \]

其中：

• dp[i-1][j] 表示从上面格子来的路径数；
• dp[i][j-1] 表示从左边格子来的路径数。

3. 边界条件

• 第一行 (i=0)：只能一直向右走，所以 dp[0][j] = 1（只有一条路径）。
• 第一列 (j=0)：只能一直向下走，所以 dp[i][0] = 1。

4. 逐步推导（以 m=3, n=3 为例）

初始化 dp 表（3x3）：

计算 dp[1][1]：

\[dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2 \]

计算 dp[1][2]：

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

计算 dp[2][1]：

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

计算 dp[2][2]：

\[dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6 \]

最终结果：dp[2][2] = 6。

5. 算法实现（Python）

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    
    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)
空间复杂度：O(m × n)，可优化到 O(n) 用一维数组。

6. 空间优化

因为当前行只依赖上一行，可以只保留一行数据：

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]
    return dp[n-1]

• 初始 dp 表示第一行的路径数。
• 每次迭代更新 dp[j] 时，dp[j] 是上一行的值（即从上面来），dp[j-1] 是当前行左边的值（即从左边来）。

7. 组合数学方法（补充）

从起点到终点需要移动 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)!} \]

例如 m=3, n=3：

\[C(4, 2) = \frac{4!}{2!2!} = 6 \]

这样我们就从问题理解、状态定义、边界处理、表格推导、代码实现到空间优化和数学方法，完整地讲解了「不同路径」问题。