62. 不同路径

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

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

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

实现

下面分别给出基于动态规划的空间优化写法——C++ 与 Python 两种实现，均为 $O(mn)$ 时间、$O(n)$ 空间：

#include <bits/stdc++.h>
using namespace std;// 计算从 (0,0) 到 (m-1,n-1) 的不同路径数
int uniquePaths(int m, int n) {// dp[j] 表示当前行到达列 j 的路径数vector<int> dp(n, 1);// 第一行所有 dp[j] 初始化为 1（只能一直向右走）for (int i = 1; i < m; ++i) {// 第 0 列始终为 1（只能一直向下走）for (int j = 1; j < n; ++j) {// 来自上方 (上一行同列) + 来自左方 (当前行前一列)dp[j] += dp[j - 1];}}return dp[n - 1];
}int main() {int m, n;// 读入 m, ncin >> m >> n;cout << uniquePaths(m, n) << "\n";return 0;
}

def unique_paths(m: int, n: int) -> int:"""dp[j] 表示当前行到达列 j 的路径数。初始 dp[:] = [1,1,...,1]，代表第 0 行只能一直向右。"""dp = [1] * nfor _ in range(1, m):# dp[0] 保持为 1for j in range(1, n):dp[j] += dp[j - 1]return dp[-1]if __name__ == "__main__":# 输入格式：m nm, n = map(int, input().split())print(unique_paths(m, n))

思路回顾：

1. 定义状态：用一维数组 dp[j] 表示「到达当前行第 $j$ 列的路径数」。

2. 边界条件：第一行所有 dp[j]=1（只能向右），第一列隐式保持 dp[0]=1（只能向下）。

3. 状态转移：对于第 $i$ 行的第 $j$ 列，有

   $$dp[j]\leftarrow dp[j](\text{上一行同列})+dp[j-1](\text{当前行前一列}).$$

4. 结果保存在 dp[n-1] 或 dp[-1]。

这种「滚动数组」的做法将空间复杂度从 $O(mn)$ 降至 $O(n)$。

---

---

---

通俗解释

下面我们用最直观的“走格子填数字”的方式来理解这道题的动态规划解法。

---

一、问题回顾

• 机器人在一个 $m\times n$ 的网格里，只能「向右」或「向下」走一步，问从左上角到右下角一共有多少条不同的路径。

---

二、最通俗的思路：给每个格子“打分”

1. 把网格想象成一个表格，我们给每个格子 $(i,j)$ 一个数 dp[i][j]，它代表「到达 $(i,j)$ 的不同走法数」。

2. 为什么格子 $(i,j)$ 的分数==它上面格子 + 它左边格子的分数？

   • 因为机器人最后一步，要么从上面 $(i-1,j)$ 下来，要么从左边 $(i,j-1)$ 右来。

   • 所以，

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

3. 边界条件：第一行和第一列只能走一条路线

   • 第一行 $(0,0)\to (0,1)\to \cdots$ 全是「一直向右」，所以它们 dp[0][*] = 1。
   • 第一列 $(0,0)\to (1,0)\to \cdots$ 全是「一直向下」，所以它们 dp[*][0] = 1。

---

三、举例：3×3 网格

我们把 dp 表格画出来（行列都从 0 开始）：

i\j	0	1	2
0	1	1	1
1	1
2	1

• 第一行、第一列先填 1。

接下来按行、按列填：

1. 填 $(1,1)$：上面是 $(0,1)=1$，左边是 $(1,0)=1$，1+1=2
2. 填 $(1,2)$：上面是 $(0,2)=1$，左边是 $(1,1)=2$，1+2=3
3. 填 $(2,1)$：上面是 $(1,1)=2$，左边是 $(2,0)=1$，2+1=3
4. 填 $(2,2)$：上面是 $(1,2)=3$，左边是 $(2,1)=3$，3+3=6

最终表格：

i\j	0	1	2
0	1	1	1
1	1	2	3
2	1	3	6

右下角 $(2,2)$ 就是 6，也就是 3×3 网格的答案。

---

四、滚动数组优化到只用一维

其实我们只需要「上一行」和「当前行」信息，就能把二维压成一维。

• 用一个长度为 $n$ 的数组 dp[j] 表示「当前行到第 $j$ 列的路径数」。

• 每次更新时：

  dp[j] = dp[j]（上面的旧值） + dp[j-1]（左边刚更新的值）
  

• 第一行先把 dp[:] = [1,1,1,...] 初始化好。

---

五、代码实现

1. C++ 版（$O(n)$ 空间）

#include <bits/stdc++.h>
using namespace std;int uniquePaths(int m, int n) {vector<int> dp(n, 1);  // 第一行：到每列只有 1 种走法for (int i = 1; i < m; ++i) {       // 从第 2 行开始for (int j = 1; j < n; ++j) {   // 第一列 dp[0] 始终是 1dp[j] += dp[j - 1];         // 上 + 左}}return dp[n - 1];
}int main() {int m, n;cin >> m >> n;cout << uniquePaths(m, n) << "\n";return 0;
}

2. Python 版（$O(n)$ 空间）

def unique_paths(m: int, n: int) -> int:dp = [1] * n           # 第一行：全 1for _ in range(1, m):  # 从第 2 行开始for j in range(1, n):dp[j] += dp[j - 1]  # 上 + 左return dp[-1]if __name__ == "__main__":m, n = map(int, input().split())print(unique_paths(m, n))

---

六、结题思路小结

1. 状态定义：dp[i][j]（或滚动数组里的 dp[j]）表示「到达格子 $(i,j)$ 的路径数」。
2. 状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1] —— 最后一部要么从上面下来，要么从左边来。
3. 边界：第一行/第一列只能一直往右/往下，路径数都是 1。
4. 空间优化：因为只用到「上一行」信息，可以把二维压成一维，dp[j] = dp[j] + dp[j-1]。

这样逻辑就很清晰：

• 想象你在走格子，每个格子都“接收”来自上方和左方的走法数；
• 一圈圈填下去，最后在终点就能看到总路数。

希望这样的流程化、填表式讲解能帮助你彻底搞懂！