def uniquePathsWithObstacles(self, obstacleGrid): m, n, dp = len(obstacleGrid), len(obstacleGrid), [0, 1] dp +=  * (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]
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?
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.