題目
思路
每走一步都會是一個 unique path，到終點的路線是由每一步所組成的，所以可以用遞迴的方式來想，最小的可重複動作就是一步，點 (i, j) 到終點的 unique path count 就是 (i + 1, j) 和 (i, j + 1) 的 unique path count 的和
最小可重複動作
return u_paths(i + 1, j) + u_paths(i, j + 1)終止條件
1
2
3
4if i >= m or j >= n:
return 0
if i == m - 1 and j == n - 1:
return 1- 已經在終點上了，unique path count 卻是 1，一開始可能會覺得有點怪，不過從終點左邊那個點來想，就不會怪了：
- 左邊那個點的 unique path count = (它的下面那點的 path count) + (它右邊那點的 path count)
- 下面那點：path count 為 0
- 右邊那點 (終點)：path count 必須是 1
- 左邊那個點的 unique path count = (它的下面那點的 path count) + (它右邊那點的 path count)
- 已經在終點上了，unique path count 卻是 1，一開始可能會覺得有點怪，不過從終點左邊那個點來想，就不會怪了：
遞迴解法如下，但時間複雜度 O(2^(m + n)) 太大了 (計算參考這篇)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def uniquePaths(self, m: int, n: int) -> int:
def u_paths(i, j):
"""
i, j 為從 0 開始的坐標
@return 由 (i, j) 走到終點的 unique path count
"""
# 終止條件
if i >= m or j >= n:
return 0
if i == m - 1 and j == n - 1:
return 1
# 最小可重複動作
return u_paths(i + 1, j) + u_paths(i, j + 1)
return u_paths(0, 0)- 空間複雜度：O(m + n)
- 因為遞迴深度為
m + n
- 因為遞迴深度為
- 空間複雜度：O(m + n)
因為同一個點可能會走到很多次，我們可以把結果存在二維陣列，避免重複計算，以減少時間複雜度
Python3 solution:
1 | def uniquePaths(self, m: int, n: int) -> int: |
- 時間複雜度：O(m * n)
- 因為有記憶，每個點只會計算一次，共有
m * n個點
- 因為有記憶，每個點只會計算一次，共有
- 空間複雜度：O(m * n)
- 維護
dp所需空間。遞迴呼叫所需空間m和n可忽略
- 維護
類似題：