LeetCode 筆記 - 64. Minimum Path Sum

Posted on

題目在此 64. Minimum Path Sum

給一個 matrix，請計算出從左上到右下最小成本路徑

解題思維

同學，不要猶豫了
還有比這題更 Dynamic programming 的嗎？
用下去吧

程式碼

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 minPathSum(self, grid: List[List[int]]) -> int:
        
        size_y = len(grid)
        size_x = len(grid[0])
        
        if size_x == 1 or size_y == 1:
            return sum(map(sum, grid))
        
        dp = [[0 for _ in range(size_x)] for _ in range(size_y)]
        dp[0][0] = grid[0][0]
        
        for y in range(size_y):
            for x in range(size_x):
                if y == 0 and x == 0:
                    continue
                if y == 0:
                    dp[y][x] = dp[y][x - 1] + grid[y][x]
                elif x == 0:
                    dp[y][x] = dp[y - 1][x] + grid[y][x]
                else:
                    dp[y][x] = min(dp[y - 1][x], dp[y][x - 1]) + grid[y][x]
                
        return dp[size_y - 1][size_x - 1]

相關文章