Python DP Solution


  • 1
    class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            rows = len(obstacleGrid)
            cols = len(obstacleGrid[0])
            dp = [[0 for i in range(cols)] for j in range(rows)]
            for i in range(rows-1, -1, -1):
                for j in range(cols-1, -1, -1):
                    if obstacleGrid[i][j] == 1:
                        dp[i][j] = 0
                    else:
                        if i == rows-1 and j == cols-1:
                            dp[i][j] = 1
                        elif i == rows - 1:
                            dp[i][j] = dp[i][j+1]
                        elif j == cols -1:
                            dp[i][j] = dp[i+1][j]
                        else:
                            dp[i][j] = dp[i+1][j] + dp[i][j+1]
            return dp[0][0]
    

Log in to reply
 

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