跳转至

62. 不同路径（Unique Paths）

频次 ★★★ · 难度 🟡 · 高频：全厂

题目

m×n 网格，从左上到右下每次只能右或下，求不同路径总数。

示例： 

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

思路

组合数学：总共需要走 m-1 步向下 + n-1 步向右，共 m+n-2 步，选其中 m-1 步向下：C(m+n-2, m-1)。

DP：dp[i][j] = dp[i-1][j] + dp[i][j-1]，与最小路径和模板一致。

代码

// 组合数学版 O(min(m,n))
public int uniquePaths(int m, int n) {
    long ans = 1;                     // long 防中间溢出
    int k = Math.min(m - 1, n - 1);   // 取较小的，减少循环
    for (int i = 1; i <= k; i++) {
        ans = ans * (m + n - 2 - i + 1) / i;
    }
    return (int) ans;
}

// DP 版
public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

状态方程发现四链（初学怎么"想到"转移方程）

  1. "最后一步"反推法：枚举到达终点的最后动作（62 里是"上或左"两种）——题面的动作规则即分类的完备清单，dp[i][j] = dp[i-1][j] + dp[i][j-1]
  2. 无后效性检查：dp 语义"路径数"对后续格子恰好够用（未来只问状态值）；反例：语义里混入"是否经过某格"就信息不足写不出方程
  3. 暴力递归 → 记忆化 → 逐行改写：递归式＝转移方程、递归边界＝初始化——把灵感题变翻译题的最万能路径
  4. 相邻格倒推口诀：画小网格问"当前格由哪几格推出"——网格类只有相邻 2~4 格参与

组合数是 62 的另一种压缩形式

共 m+n-2 步选 m-1 步向下 → C(m+n-2, m-1)，O(min(m,n))。与 DP 是同一搜索空间的两种遍历（对照 78：位掩码=决策树压平，DP=按序遍历）。面试可甩一句加分。

网格类公式家族（62/63/64 同底盘）

dp[i][j] = dp[i-1][j] + dp[i][j-1]   （62 计数）
dp[i][j] = min(...) 或 max(...)      （64 最小路径和）
dp[i][j] = 障碍为 0 时才递推         （63 加障碍）
初始化：第一行/列"别无选择"处为 1（62）或“障碍即断”为 0（63），累加规则变化只发生在"续传细则"

复杂度

  • 组合数学：O(min(m,n)) 时间，O(1) 空间
  • DP：O(m×n) 时间，O(n) 空间

边界条件

  • m=1 或 n=1：只有一条路径

变式

易错点

  • 组合数计算时用 long 防中间溢出，边乘边除
  • DP 版 dp 数组初始化为 1（第一行只有一条路径）

面试追问

  • 组合数学法的推导？ 一共 m+n-2 步，选 m-1 步向下，等价于 n-1 步向右。答案 C(m+n-2, m-1)

关联题