LeetCode 筆記 - 63. Unique Paths II

Posted on

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

相關文章