LeetCode 筆記 - 62. Unique Paths

Posted on

題目在此 62. Unique Paths

給一個地圖，請給出從左上走到右下的所有路徑走法數量

解題思維

各位同學，這題不用懷疑就是 Dynamic programming 用下去就對了

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        
        length_y = m
        length_x = n
        
        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 y > 0:
                    count_map[y][x] += count_map[y - 1][x]
                if x > 0:
                    count_map[y][x] += count_map[y][x - 1]
        
        return count_map[-1][-1]

相關文章