Python DP beats 99.9%, O(n) space


  • 0
    X
    def uniquePathsWithObstacles(self, obstacleGrid):
            temp = [1]+[0]*(len(obstacleGrid[0])-1)
            for row in obstacleGrid:
                cur = []
                for i,obstacle in enumerate(row):
                    if obstacle:
                        cur.append(0)
                    else:
                        cur.append(temp[i]+(cur[-1] if cur else 0))
                temp = cur
            return temp[-1]

Log in to reply
 

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