Unique Paths 解題教學:3 種解法完整比較|LeetCode 62 Best Practice

Unique Paths 解題教學示意圖|LeetCode 62

本文完整拆解 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 演算法步驟

  1. 建立長度為 n 的一維陣列 dp,全部初始化為 1(代表第一列每格只有一條路徑)。
  2. 從第二列開始,逐列更新。
  3. 每一列由左到右走訪,令 dp[j] = dp[j] + dp[j-1](右邊是上方,左邊是左方)。
  4. 全部更新完後,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)本文採用