LeetCode 筆記 - 64. Minimum Path Sum

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

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

解題思維

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

程式碼

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]

解題思維

程式碼

也許你也會想看看