本文完整拆解 LeetCode 62 Unique Paths 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Unique Paths 一次弄懂。
Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
Example 1:

Input: m = 3, n = 7 Output: 28
Example 2:
Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down
Constraints:
1 <= m, n <= 100
Python
from functools import lru_cache
class Solution:
@lru_cache(None)
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)
Unique Paths 解題思路
機器人只能往右或往下,所以抵達每一格的路徑數,就等於「從上面來」加上「從左邊來」的路徑數之和。這讓整張表格可以由左上往右下一格一格推出來;再觀察到計算第 i 列時只會用到第 i-1 列,就能把二維表格壓成一維滾動陣列。
Unique Paths 演算法步驟
- 建立長度為 n 的一維陣列 dp,全部初始化為 1(代表第一列每格只有一條路徑)。
- 從第二列開始,逐列更新。
- 每一列由左到右走訪,令 dp[j] = dp[j] + dp[j-1](右邊是上方,左邊是左方)。
- 全部更新完後,dp[n-1] 就是答案。
Unique Paths 複雜度分析
| 項目 | 複雜度 |
|---|---|
| 時間複雜度 | O(m·n) |
| 空間複雜度 | O(n) |
需要填滿 m×n 個狀態,時間為 O(m·n)。滾動陣列只保留一列,空間從 O(m·n) 壓到 O(n)。若改用組合數公式 C(m+n-2, m-1) 甚至可達 O(min(m,n)) 時間。
Unique Paths 的邊界情況與常見錯誤
- m 或 n 為 1 時答案是 1,滾動陣列的初始值已經涵蓋這個情況。
- dp[0] 永遠是 1,更新時 j 要從 1 開始,否則會存取 dp[-1]。
- 格數大時答案會非常大,注意整數溢位。
- 若題目加入障礙物,就要改成 Unique Paths II 的版本,障礙格設為 0。
Unique Paths 其他解法比較
| 解法 | 時間 | 空間 | 說明 |
|---|---|---|---|
| 遞迴列舉所有路徑 | O(2^(m+n)) | O(m+n) | 指數爆炸,只能跑極小測資 |
| 二維動態規劃表格 | O(m·n) | O(m·n) | 最好理解的版本 |
| 一維滾動陣列 | O(m·n) | O(n) | 本文採用 |
