⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。
題目在此 63. Unique Paths II
![image 31]()
給一個 m x n 的地圖，機器人固定從最左上走到最右下，只能選擇往下或往右
請計算出有多少種可能
解題思維
這題明顯就是 Dynamic programming 的應用
演算法核心就是因為機器人只能往右或往下，而當走到某一格就把上方跟左邊的數字加起來就可以了
而起點設定為 1 代表目前的所有可能
完成 ☺️
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def uniquePathsWithObstacles(self, g: List[List[int]]) -> int:
if g[-1][-1] == 1 or g[0][0] == 1:
return 0
length_y = len(g)
length_x = len(g[0])
count_map = [[0 for _ in range(length_x)] for _ in range(length_y)]
count_map[0][0] = 1
for y in range(length_y):
for x in range(length_x):
if g[y][x] == 1 or count_map[y][x] == 1:
continue
if y > 0 and g[y - 1][x] == 0:
count_map[y][x] += count_map[y - 1][x]
if x > 0 and g[y][x - 1] == 0:
count_map[y][x] += count_map[y][x - 1]
return count_map[-1][-1]
|
也許你也會想看看
