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 ?$ 全是「一直向右」，所以它們 dp[0][*] = 1。
   • 第一列 $(0,0)\to (1,0)\to ?$ 全是「一直向下」，所以它們 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]。

這樣邏輯就很清晰：

• 想象你在走格子，每個格子都“接收”來自上方和左方的走法數；
• 一圈圈填下去，最后在終點就能看到總路數。

希望這樣的流程化、填表式講解能幫助你徹底搞懂！