DP solution in python, beats 93% submissions


  • 0
    M

    For each cell (i,j) you need to check the optimal solution at above (i-1,j) and the one to the left (i,j-1) since one can only move down or to the right. O(mn) complexity with O(n) space.

        def minPathSum(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            if not grid: return 0
            m,n = len(grid), len(grid[0])
            prevrow = [0]*(n+1)
            prevrow[0] = float('inf')
            
            for j in range(1,n+1):
                prevrow[j] = sum(grid[0][:j])
            if m == 1: return prevrow[n]
            for i in range(1,m):
                currrow = [0]*(n+1)
                currrow[0] = float('inf') 
                for j in range(1,n+1):
                    currrow[j] = min(prevrow[j], currrow[j-1]) + grid[i][j-1]
                prevrow = currrow
            return currrow[n]
    

Log in to reply
 

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