# [Algorithm] Leetcode #63 Unique Paths II (DP/Medium/C++)

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)