Unique Paths（不同路径）

题目 / Problem

中文： 一个机器人位于 m × n 网格的左上角 grid[0][0]，需要移动到右下角 grid[m - 1][n - 1]。

机器人每次只能向右或向下移动一步。给定整数 m 和 n，返回机器人到达右下角的不同路径数量。

测试数据保证答案不超过 2 × 10^9。

English: A robot starts at the top-left corner grid[0][0] of an m × n grid and must reach the bottom-right corner grid[m - 1][n - 1].

The robot may move only one step right or one step down at a time. Given m and n, return the number of unique paths to the bottom-right corner.

The test cases guarantee that the answer is at most 2 × 10^9.

示例 / Examples

Example 1

Input:  m = 3, n = 7
Output: 28

机器人从 3 × 7 网格左上角移动到右下角 / Robot moving from the top-left to the bottom-right of a 3 × 7 grid

Example 2

Input:  m = 3, n = 2
Output: 3

三条路径分别为：
The three paths are:

1. Right → Down → Down
2. Down → Down → Right
3. Down → Right → Down

解题思路：动态规划 / Approach: Dynamic Programming

对于网格中的任意位置 (row, column)，机器人只能从两个方向到达：
For any position (row, column), the robot can arrive from only two directions:

从上方 (row - 1, column) 向下移动。
Move down from (row - 1, column).
从左侧 (row, column - 1) 向右移动。
Move right from (row, column - 1).

因此，到达当前位置的路径数量等于上方和左侧路径数量之和：
Therefore, the number of paths to the current cell is the sum of the paths from above and from the left:

dp[row][column] = dp[row - 1][column] + dp[row][column - 1]

初始状态 / Base Cases

第一行中的每个位置只能一直向右到达，因此路径数都是 1。
Every cell in the first row can only be reached by moving right, so each has one path.

第一列中的每个位置只能一直向下到达，因此路径数也都是 1。
Every cell in the first column can only be reached by moving down, so each also has one path.

1 1 1 1 ...
1
1
1
⋮

二维 DP 示例 / Two-Dimensional DP Example

对于 m = 3、n = 3：
For m = 3 and n = 3:

1  1  1
1  2  3
1  3  6

例如，中间位置的路径数为：
For example, the center cell has:

1（来自上方 / from above）+ 1（来自左侧 / from left）= 2

右下角的值 6 就是最终答案。
The bottom-right value 6 is the final answer.

空间优化：一维 DP / Space Optimization: One-Dimensional DP

计算当前行时，只需要当前列原来的值（来自上方）和左侧刚更新的值。
While computing the current row, only the old value at the current column (from above) and the newly updated value to the left are needed.

因此可以使用一维数组：
Therefore, use a one-dimensional array:

dp[column]     = 更新前来自上方的路径数
dp[column - 1] = 当前行左侧的路径数

状态更新为：
The transition becomes:

dp[column] = dp[column] + dp[column - 1];

数组初始全部设为 1，表示第一行每个位置都只有一条路径。
Initialize every entry to 1, representing the single path to every cell in the first row.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);

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

  return dp[n - 1];
}

执行过程 / Walkthrough

以 m = 3、n = 7 为例：
For m = 3 and n = 7:

第一行 / First Row

[1, 1, 1, 1, 1, 1, 1]

第二行 / Second Row

从左到右执行 dp[column] += dp[column - 1]：
Apply dp[column] += dp[column - 1] from left to right:

[1, 2, 3, 4, 5, 6, 7]

第三行 / Third Row

[1, 3, 6, 10, 15, 21, 28]

最后一个位置为 28，因此共有 28 条不同路径。
The final entry is 28, so there are 28 unique paths.

为什么必须从左到右更新？ / Why Update Left to Right?

更新 dp[column] 时：
When updating dp[column]:

dp[column] 尚未更新，表示上方的路径数。
dp[column] has not yet been updated and represents the value from above.
dp[column - 1] 已经更新，表示当前行左侧的路径数。
dp[column - 1] has already been updated and represents the value from the left in the current row.

如果从右向左更新，dp[column - 1] 仍然是上一行的数据，状态转移就会错误。
If updated from right to left, dp[column - 1] would still belong to the previous row, producing an incorrect transition.

另一种方法：组合数学 / Alternative: Combinatorics

从左上角到右下角，无论具体顺序如何，机器人一定需要：
Regardless of order, the robot must make exactly:

m - 1 次向下移动 / down moves
n - 1 次向右移动 / right moves

总步数为 m + n - 2。只需从这些步骤中选择哪些位置放置向下移动：
There are m + n - 2 total moves. Choose which positions contain the downward moves:

C(m + n - 2, m - 1)

也可以选择向右移动的位置：
Equivalently, choose the right moves:

C(m + n - 2, n - 1)

组合数学可以把时间降为 O(min(m, n))，但实现时需要注意中间结果和浮点精度。动态规划更直观，也足以满足本题约束。
The combinatorial approach can run in O(min(m, n)) time, but its implementation must handle intermediate values and floating-point precision carefully. Dynamic programming is more direct and easily satisfies the constraints.

复杂度 / Complexity

时间复杂度 / Time: O(m × n)
空间复杂度 / Space: O(n)

如果希望占用更少空间，可以让一维数组长度等于 min(m, n)，因为交换网格的行列不会改变路径数量。
To minimize memory further, use an array of length min(m, n), since swapping the grid dimensions does not change the path count.

易错点 / Common Pitfalls

第一行和第一列的路径数都应初始化为 1。
Initialize path counts in the first row and first column to 1.
一维 DP 必须从左到右更新。
Update the one-dimensional DP from left to right.
循环应从下标 1 开始，因为第 0 行和第 0 列是初始边界。
Start loops at index 1 because row 0 and column 0 form the base boundaries.
当 m === 1 或 n === 1 时，只有一条路径，当前实现会自然返回 1。
When m === 1 or n === 1, there is only one path, and the implementation naturally returns 1.
机器人只能向右或向下，不能回退或斜向移动。
The robot may move only right or down—never backward or diagonally.

Unique Paths