python dp O(m*n) time O(m) space


  • 0
    W

    '''

    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid: return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [1] * n
        for i in range(n):
            if obstacleGrid[0][i] == 1:
                dp[i:] = [0] * (n - i)
                break
        for i in range(1, m):
            if obstacleGrid[i][0] == 1:
                dp[0] = 0
            for j in range(1, n):
                dp[j] = 0 if obstacleGrid[i][j] == 1 else dp[j-1] + dp[j]
        return dp[-1]
    

    '''


Log in to reply
 

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