This question is a modified version of #62 Unique Paths.
One constraint is added which is there might be an obstacle on the grid. How do we deal with this?
First, we need to understand the recurrence relation. As you might’ve seen my previous post for #62, dp[i][j] = dp[i-1][j] + dp[i][j-1] with the base condition dp[0][0] = 1 . dp[i][j] refers to # of ways to reach (i , j) from (0,0). Then, if there’s an obstacle at the (i , j) position, what would be the possible number of ways to get to that point? The answer is obviously 0! You cannot make the destination where there’s an obstacle.
Note that in line 5, this condition should come before line 6 since if not, the program would handle the case where grid is [[1]] in a wrong way, returning 1, not 0.
Top down Approach
Time Complexity: O(n*m)
