Easy understand python DP with comments


  • 1

    This is the simple code to solve this problem, it's very easy to understand. Also, it might not the best solution. However, it's human readable when you take an interview. We also can make the code more simple and efficient.

        def uniquePathsWithObstacles(obstacleGrid):
            row=len(obstacleGrid)
            col=len(obstacleGrid[0])
             
            dp=[[1 for _ in xrange(col)] for _ in xrange(row)]
            
            # if check the `1` in the first row, the right part all set 0
            for i in xrange(row):
                if obstacleGrid[i][0]==1:
                    for k in xrange(i,row):
                        dp[k][0]=0
                    break
            # if check one `1` in the first column the bottom next set 0
            for j in xrange(col):
                 if obstacleGrid[0][j]==1:
                    for k in xrange(j,col):
                        dp[0][k]=0
                    break
            
            # check the dp[i][j]
            for i in xrange(1,row):
                for j in xrange(1,col):
                    # if face obstacle, set dp[i][j] to 0
                    if obstacleGrid[i][j]==1:
                        dp[i][j]=0
                    else:
                        dp[i][j]=dp[i-1][j]+dp[i][j-1]
                    
            return dp[row-1][col-1]
    

  • 0

    Then make it as the constant space:

            row=len(obstacleGrid)
            col=len(obstacleGrid[0])
            # star with 1 return 0
            if obstacleGrid[row-1][col-1] == 1 or obstacleGrid[0][0] == 1:
                return 0
                    
            dp=[0 for _ in xrange(col)]
            dp[0]=1
            
            # deal with the first row--if only one row
            for j in xrange(1,col):
                if obstacleGrid[0][j]==1:
                    dp[j]=0
                else:
                    dp[j]=dp[j-1]
                
            # check the dp[i][j]..the 1---row
            for i in xrange(1,row):
                for j in xrange(0,col):
                    # deal with the first column
                    if j==0:
                        if obstacleGrid[i][j]==1:
                            dp[j]=0
                    else:
                        # if face obstacle, set dp[i][j] to 0
                        if obstacleGrid[i][j]==1:
                            dp[j]=0
                        else:
                            dp[j]=dp[j]+dp[j-1]
                        
            return dp[col-1]
    

Log in to reply
 

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