64. Minimum Path Sum

Loading...LeetCode

初看以为是BFS（爬格子），细品发现是DP题（find minimum），因为只考虑往下和往右走，简单了很多，可以借助hashmap（v1），也可以直接 bottom-up DP。

如果 follow-up 变成可以往左和往上走，情况会复杂不少（不记录path的话会绕圈圈），heap会是个更好的选择。

v1

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = dict()
        dp[(0, 0)] = grid[0][0]
        
        def backSearch(y, x):
            if (y, x) in dp: 
                return dp[(y, x)]
            prev = [backSearch(a, b) for (a, b) in [(y, x-1), (y-1, x)] if 0<=a<m and 0<=b<n]
            dp[(y, x)] = grid[y][x] + min(prev)
            return dp[(y, x)]
        
        return backSearch(m-1, n-1)

v2

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[0][0] = grid[0][0]
        
        for y in range(1, m):
            dp[y][0] = dp[y-1][0] + grid[y][0]
        for x in range(1, n):
            dp[0][x] = dp[0][x-1] + grid[0][x]
            
        for y in range(1, m):
            for x in range(1, n):
                dp[y][x] = min(dp[y-1][x], dp[y][x-1]) + grid[y][x]
        
        return dp[m-1][n-1]

follow-up

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        prQ = [(grid[0][0], 0, 0)]
        visited = set()
        
        while prQ:
            cost, y, x = heapq.heappop(prQ)
            if y == m-1 and x == n-1:
                return cost
            if (y, x) in visited:
                continue
            # to fit the original question, drop the two extra neighbors.
            neighbors = [(a,b) for (a,b) in [(y+1,x), (y-1,x), (y,x+1), (y,x-1)] if 0<=a<m and 0<=b<n]
            for (a, b) in neighbors:
                heapq.heappush(prQ, (cost+grid[a][b], a, b))
            
            visited.add((y, x))