Python 42ms DP solution


  • 0
    K

    Use DP solution, readable code below.

    class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            if obstacleGrid[0][0] == 1:
                return 0
            
            dp = {}
            for i in xrange(len(obstacleGrid[0])):
                if obstacleGrid[0][i] == 1:
                    dp[i] = 0
                else:
                    if i-1 in dp:
                        dp[i] = dp[i-1]
                    else:
                        dp[i] = 1
                
            for i in xrange(1, len(obstacleGrid)):
                dp[0] = 0 if obstacleGrid[i][0] == 1 else dp[0]
                for j in xrange(1, len(obstacleGrid[0])):
                    dp[j] = 0 if obstacleGrid[i][j] == 1 else dp[j] + dp[j-1]
                    
            return dp[len(obstacleGrid[0])-1]
    

Log in to reply
 

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