[LeetCode][python3]Day18. Minimum Path Sum (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.18

1. My Solution

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        maxrow=len(grid)
        maxcol=len(grid[-1])
        check={(0,0)}
        pathsum=[[0]*maxcol for i in range(maxrow)]
        pathsum[0][0]=grid[0][0]
        while check:
            row,col=check.pop()
            cursum=pathsum[row][col]
            if maxrow>row+1>=0:
                if pathsum[row+1][col]==0 or pathsum[row+1][col]>cursum+grid[row+1][col]:
                    pathsum[row+1][col]=cursum+grid[row+1][col]
                    check.add((row+1,col))
            if maxcol>col+1>=0:
                if pathsum[row][col+1]==0 or pathsum[row][col+1]>cursum+grid[row][col+1]:
                    pathsum[row][col+1]=cursum+grid[row][col+1]
                    check.add((row,col+1))
        return pathsum[-1][-1]

Explanation:

The Solution is so slow that it didn’t show on the Runtime map. The check stack is used to save the "To do list”. It is so slow because there are at most 2*m*n pop() and add() functions, which cost lots of times.

2. A Better Solution

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:     
        for i in range(1, len(grid[0])):
            grid[0][i] += grid[0][i-1]   
        for i in range(1, len(grid)):
            grid[i][0] += grid[i-1][0]
        for i in range(1, len(grid)):
            for j in range(1, len(grid[0])):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1]) 
        return grid[-1][-1]

Explanation:

This Solution calculates the first row and the first column, which won’t be affect by other elements because you can only move either down or right in this problem. Since every point must come from up or left, the solution calculates the min path from top left to bottom right.