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:
                    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]
                        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.