Python DP solution, easy to understand


  • 0
    class Solution(object):
        def minPathSum(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            m,n = len(grid),len(grid[0])
            dp = list(grid)
            for i in range(m):
                for j in range(n):
                    if i == 0 and j == 0:
                        pass
                    elif i == 0 and j > 0:
                        dp[i][j] = dp[i][j-1]+grid[i][j]
                    elif i > 0 and j == 0:
                        dp[i][j] = dp[i-1][j]+grid[i][j]
                    else:
                        dp[i][j] = min(grid[i-1][j],grid[i][j-1])+grid[i][j]
            return dp[-1][-1]
    

    Generate a DP array to store results. For the general case, dp[i][j] = min(grid[i-1][j],grid[i][j-1])+grid[i][j], then deal with cases of the first row and the first column.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.