Dynamic Programming code in python with O(m) space


  • 0
    B
    class Solution:
    # @param grid, a list of lists of integers
    # @return an integer
    def minPathSum(self, grid):
        rows=len(grid)
        if rows==0:
            return 0
        cols=len(grid[0])
        
        paths=[0]*cols
        
        paths[0]=grid[0][0]
        
        for j in range(1,cols):
            paths[j]=paths[j-1]+grid[0][j]
        
        for i in range(1,rows):
            for j in range(0,cols):
                if j!=0:
                    paths[j]=min(paths[j-1],paths[j])+grid[i][j]
                else:
                    paths[j]=paths[j]+grid[i][j]
                    
        return paths[cols-1]
    

    DP using a single row to store path length data. Since the previous row is used immediately and rows before that are discarded. There is no need to remember all n*m data.


Log in to reply
 

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