不同路径
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
一个机器人位于一个 m x n 网格的左上角（起始点标记为「Start」）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（标记为「Finish」）。
问总共有多少条不同的路径？
示例 1
示例 2
示例 3
模拟答题者思考
1. 最直接：从起点 DFS/BFS 枚举所有「只向右或向下」的路径，每走到右下角计数 +1——正确但指数级，m,n 可达 100 会超时。
2. 重复在哪里？到达 (i,j) 的路径，最后一步要么从 (i-1,j) 来，要么从 (i,j-1) 来；两种来源的路径条数互不相交，可以相加——典型的最优子结构。
3. 子问题定义：设 dp[i][j] = 到 (i,j) 的路径数。递推 dp[i][j] = dp[i-1][j] + dp[i][j-1]；边界第一行/列全为 1（只能一直走一个方向）。
4. 手推 m=3, n=2：DP 表为 [[1,1],[1,2],[1,3]]，右下角 dp[2][1]=3，与示例 2 一致。
5. 组合数学视角：总共走 m+n-2 步，其中 m-1 步向下，答案为 C(m+n-2, m-1)；但 DP 思路更通用（#63 有障碍物时组合公式不好直接套）。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dp[i][j] | int[][] | 定义：从左上角 (0,0) 走到格子 (i,j) 的不同路径条数维护：每个格子只能从上方或左方来，故 dp[i][j] = dp[i-1][j] + dp[i][j-1]更新：按行优先双重循环， i 从 0 到 m-1、j 从 0 到 n-1 递增填表 |
dp[0][*] / dp[*][0] | int | 定义：第一行、第一列格子的路径数边界 维护：起点到同行/同列任意格只能一直向右或一直向下，每条路径唯一 更新：全部初始化为 1；若 i==0 或 j==0 时直接设 dp[i][j]=1，无需递推 |
prev / cur | int[] | 定义：空间优化时的一维滚动数组，cur[j] 表示当前行第 j 列的路径数维护：每算完一行， prev = cur 作为下一行的「上方」来源更新： cur[j] = prev[j] + cur[j-1]（上方 + 左方），首列 cur[0]=1 |
m, n | int | 定义：网格的行数与列数 维护：只读输入，决定 DP 表规模和最终答案位置 dp[m-1][n-1]更新：范围 1 ≤ m,n ≤ 100，答案不超过 2×10⁹ |
落码步骤
1. 创建 dp[m][n]，第一行、第一列全部填 1
2. 双重循环 i 从 1 到 m-1，j 从 1 到 n-1
3. dp[i][j] = dp[i-1][j] + dp[i][j-1]
4. 返回 dp[m-1][n-1]
5. （可选）空间优化：用长度 n 的一维数组滚动，每行更新 cur[j] = prev[j] + cur[j-1]
代码实现
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# dp[j]：当前行第 j 列的路径数（滚动数组）
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1] # 上方(prev[j]) + 左方(dp[j-1])
return dp[n - 1]class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n, 1); // 第一行全为 1
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // 上方 + 左方
}
}
return dp[n - 1];
}
};
// 时间 O(mn)，空间 O(n)复杂度分析
O(m × n)
O(n)（滚动数组）
常见坑
边界未初始化：第一行、第一列的路径数都是 1，不是 0；若漏初始化，dp[1][1] 会从 0 递推出错。
递推方向错误：必须从左到右、从上到下填表，保证 dp[i-1][j] 和 dp[i][j-1] 已算好；倒序遍历会得到错误答案。
滚动数组时覆盖顺序：内层 j 必须从 1 到 n-1 递增，dp[j] += dp[j-1] 中的 dp[j-1] 是本行左邻（已更新），dp[j] 更新前保存的是上一行同列值。
必测边界 Case
m = 1, n = 5 → 1（只能一直向右，唯一路径）
m = 5, n = 1 → 1（只能一直向下，唯一路径）
m = 1, n = 1 → 1（起点即终点）
m = 3, n = 3 → 6（对称情形，验证递推正确性）
m = 3, n = 7 → 28（示例 1，路径数 = C(8,2) = 28）