Pyhon DP solution


  • 2
    H
    def uniquePathsWithObstacles(self, obstacleGrid):
        m, n, dp = len(obstacleGrid), len(obstacleGrid[0]), [0, 1]
        dp += [0] * (n - 1)
        for i in xrange(1, m + 1):
            for j in xrange(1, n + 1):
                dp[j] = (not obstacleGrid[i-1][j-1]) * (dp[j] + dp[j-1]) 
        return dp[-1]

  • 0
    D

    Hi, I ended up with the same solution by try and error.
    Could you maybe give a short (idiot-proof) explanation what exactly this is doing? Why can we assume that dp[j] += dp[j-1] is valid?


  • 0
    H

    Sorry,I just saw your reply.And the time is 6 days ago,so you must have resolved it .

    dp[j]= (dp[j]+dp[j-1]) if obstacleGrid[i-1][j-1]==0 else 0 
    

    dp[j-1] means the path from left, and dp[j] on the right means the path from up.
    So if there is not a obstacle,we can update dp[i] to dp[i]+dp[-1].
    but if there is a obstacle,means we cannot reach this point,so update dp[i] to 0.


Log in to reply
 

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