#62. 不同路径

LeetCode 原题链接

#题目描述

一个机器人位于 m × n 网格的左上角，每次只能向右或向下移动一步。机器人试图到达网格的右下角，求一共有多少条不同路径。

示例：

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

输入：m = 3, n = 2
输出：3
解释：
1. 向右 -> 向下 -> 向下
2. 向下 -> 向右 -> 向下
3. 向下 -> 向下 -> 向右

#1. 为什么使用动态规划

要到达任意格子 (i, j)，最后一步只有两种可能：

• 从上方 (i - 1, j) 向下走一步。
• 从左侧 (i, j - 1) 向右走一步。

因此，到达当前格子的路径数等于到达上方和左侧格子的路径数之和。这些子问题会被反复使用，适合用动态规划保存计算结果。

#2. 状态定义与转移方程

采用从 0 开始的实际网格下标：

dp[i][j]：从左上角走到第 i 行、第 j 列的路径数量

有效下标范围为：

0 <= i < m
0 <= j < n

对于既不在第一行、也不在第一列的格子：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

因为每条到达 (i, j) 的路径，最后一步必然来自上方或左侧，而且这两类路径互不重叠。

#3. 常规初始化

第一行的每个格子只能一直向右到达，第一列的每个格子只能一直向下到达，所以路径数都是 1：

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

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

完整实现：

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));

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

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

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

  return dp[m - 1][n - 1];
};

#4. 示例推演

对于 m = 3, n = 3，初始化第一行和第一列后：

1  1  1
1  0  0
1  0  0

按照从上到下、从左到右的顺序填表：

dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

最终 DP 表为：

1  1  1
1  2  3
1  3  6

所以到达右下角共有 6 条路径。

#5. 常见错误：多创建一行一列却全部初始化为 1

下面的写法会得到错误答案：

const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

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

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

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

return dp[m][n];

问题不在转移方程，而在于状态坐标和初始化不一致。

这段代码把实际网格改成了从 (1, 1) 到 (m, n)，第 0 行和第 0 列应该是虚拟边界。但它又把两条虚拟边界全部设为 1，导致实际起点被重复计数：

dp[1][1] = dp[0][1] + dp[1][0]
         = 1 + 1
         = 2

实际上，到达起点只能算一种方式。错误从 dp[1][1] 开始，随后会传播到整个 DP 表。

#6. 哨兵初始化：为什么 dp[0][1] = 1 正确

可以保留 (m + 1) × (n + 1) 的数组，但必须明确：

• 实际网格使用从 1 开始的下标，即 (1, 1) 到 (m, n)。
• 第 0 行和第 0 列只是值为 0 的虚拟边界。
• 只在实际起点上方放置一个值为 1 的虚拟入口。

dp[0][1] = 1;

于是实际起点能够通过统一的转移公式得到正确初值：

dp[1][1] = dp[0][1] + dp[1][0]
         = 1 + 0
         = 1

这个 1 会继续自然传播：

第一行：dp[1][2] = dp[0][2] + dp[1][1] = 0 + 1 = 1
第一列：dp[2][1] = dp[1][1] + dp[2][0] = 1 + 0 = 1

完整实现：

var uniquePaths = function (m, n) {
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  dp[0][1] = 1;

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

  return dp[m][n];
};

也可以改为设置 dp[1][0] = 1，效果相同。两种写法都只为起点提供一个虚拟来源。

哨兵写法的价值在于：第一行、第一列和内部格子可以使用完全相同的转移代码，不需要单独初始化实际边界。

#7. 两套下标体系不能混用

两种正确写法的区别如下：

动态规划代码最常见的错误之一，就是状态定义采用一套下标，数组尺寸、初始化或返回位置却采用另一套下标。

检查时可以依次问：

1. dp[i][j] 对应实际网格的哪个格子？
2. 起点在 DP 表中的坐标是什么？
3. 起点应该通过初始化得到 1，还是通过转移得到 1？
4. 右下角对应 dp[m - 1][n - 1] 还是 dp[m][n]？

只要这四处定义一致，就不容易出现多一行、多一列的问题。

#8. 一维数组空间优化

计算第 i 行时，每个状态只依赖：

• 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];
    }
  }

  return dp[n - 1];
};

这里必须从左向右更新，因为当前状态依赖本行已经更新好的左侧状态 dp[j - 1]。

如果希望进一步减少空间，可以让较短的维度作为一维数组长度，使空间复杂度降为 O(min(m, n))。

#9. 复杂度分析

二维动态规划：

• 时间复杂度：O(m × n)，每个格子计算一次。
• 空间复杂度：O(m × n)，保存完整 DP 表。

一维空间优化：

• 时间复杂度：O(m × n)。
• 空间复杂度：O(n)；调整行列后可写为 O(min(m, n))。

#10. 数学解法

无论选择哪条路径，都必须完成：

• m - 1 次向下移动。
• n - 1 次向右移动。

总共移动 m + n - 2 步，只需决定其中哪些位置用于向下移动，因此答案是组合数：

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

可以逐步相乘、相除计算组合数，将额外空间降为 O(1)。不过动态规划更直观，也更容易扩展到 LeetCode 63「不同路径 II」这类存在障碍物的变体。

#11. 边界条件与易错点

• 当 m === 1 或 n === 1 时，机器人只有一条路径。
• 转移顺序必须保证上方和左侧状态已经计算完成，因此二维写法应从上到下、从左到右遍历。
• 常规写法的循环条件是 < m、< n，答案是 dp[m - 1][n - 1]。
• 哨兵写法的循环条件是 <= m、<= n，答案是 dp[m][n]。
• 哨兵边界不能全部设为 1，否则起点会被计算为 2。
• 一维压缩时不能从右向左更新，否则读取不到本行更新后的左侧状态。

#12. 可迁移总结

二维网格路径计数的基本模型是：

定义到达当前位置的方案数
  -> 枚举最后一步来自哪里
    -> 将所有互斥来源的方案数相加

本题还体现了一个重要的 DP 编码原则：数组尺寸、状态坐标、初始化、循环边界和最终返回值必须使用同一套下标体系。

增加虚拟边界并不是简单地“多开一行一列”，而是重新定义了状态坐标。哨兵值也不是实际答案，而是为了让边界状态通过统一转移自然产生的人工入口。