LeetCode 筆記 - 63. Unique Paths II

題目在此 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]

也許你也會想看看