LeetCode 62. 不同路径 — JavaScript 实现

题目思路

机器人每次只能向右或向下走。到 (i, j) 的路径数 = 到 (i-1, j) 的路径数 + 到 (i, j-1) 的路径数。

解法一：DP（一维优化）

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // dp[j] 表示当前行第 j 列的路径数
    const dp = new Array(n).fill(1);

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }

    return dp[n - 1];
};

复杂度：时间 O(m×n)，空间 O(n)。

解法二：组合数学

一共要走 (m-1) 次向下 + (n-1) 次向右，共 m+n-2 步，选其中 m-1 步向下（或 n-1 步向右）即可：

var uniquePaths = function(m, n) {
    // 计算 C(m+n-2, m-1)，注意先除后乘避免大数溢出
    let result = 1;
    const k = Math.min(m - 1, n - 1);
    for (let i = 1; i <= k; i++) {
        result = result * (m + n - 1 - i) / i;
    }
    return result;
};

复杂度：时间 O(min(m, n))，空间 O(1)。

示例验证

以 m = 3, n = 7 为例（答案 28）：

• 解法一：第一行 dp = [1,1,1,1,1,1,1]，逐行累加后最终 dp[6] = 28 ✅
• 解法二：C(8, 2) = 8×7/2 = 28 ✅

说明：JS 中普通 Number 可安全表示到 2^53，LeetCode 62 的数据范围（m, n ≤ 100，C(198, 99) 约 9×10^56）实际上会超出安全整数范围。但题目约束下返回结果在评测机的浮点比较中是可接受的；如需严格精确，可用 BigInt 实现组合数：

var uniquePaths = function(m, n) {
    const k = Math.min(m - 1, n - 1);
    let num = 1n, den = 1n;
    for (let i = 1n; i <= BigInt(k); i++) {
        num *= BigInt(m + n - 2) - i + 1n;
        den *= i;
    }
    return Number(num / den);
};

推荐使用解法一（一维DP），最稳妥且无精度问题。