不同路径

LeetCode 官方题目链接

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

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

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

思路拆解

这是一道经典的二维动态规划题目。

动态规划

1. 定义状态：dp[i][j] 表示从左上角 (0, 0) 到达 (i, j) 的不同路径数量。
2. 状态转移方程：
   • 因为机器人只能向下或向右移动，所以到达 (i, j) 只有两种可能：
     • 从上方 (i-1, j) 向下移动一步。
     • 从左方 (i, j-1) 向右移动一步。
   • 因此，dp[i][j] = dp[i-1][j] + dp[i][j-1]。
3. 初始条件：
   • 第一行的所有格子 dp[0][j] 只能从左边走过来，所以路径数都是 1。
   • 第一列的所有格子 dp[i][0] 只能从上边走过来，所以路径数都是 1。
4. 返回值：
   • dp[m-1][n-1]。

空间优化

• 由于 dp[i][j] 只依赖于上方和左方的状态，我们可以将二维数组压缩为一维数组。
• dp[j] 表示当前行第 j 列的路径数。
• 更新公式：dp[j] = dp[j] + dp[j-1]（新的 dp[j] 等于 上方的 dp[j] 加上 左边的 dp[j-1]）。

代码实现

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // 空间优化：只使用一维数组
    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] (上) + dp[j-1] (左)
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    
    return dp[n - 1];
};

运行演示

假设 m = 3, n = 2：

1. 初始化 dp = [1, 1] (对应第一行)。
2. i = 1 (第二行):
   • j = 1: dp[1] = dp[1] (1) + dp[0] (1) = 2。 dp 变为 [1, 2]。
3. i = 2 (第三行):
   • j = 1: dp[1] = dp[1] (2) + dp[0] (1) = 3。 dp 变为 [1, 3]。

返回 3。

复杂度分析

• 时间复杂度：$O(m \times n)$，需要遍历整个网格。
• 空间复杂度：$O(n)$，使用了一维数组进行优化（也可以优化到 $O(\min(m, n))$）。