**Solution**

**Unique Paths II** https://leetcode.com/problems/unique-paths-ii/?tab=Description

**Memoization**

```
from collections import defaultdict
class Solution(object):
def helper(self, i, j, M, N, grid, cache):
if 0<=i<=M-1 and 0<=j<=N-1 and grid[i][j] != 1:
if i == M-1 and j == N-1:
return 1
elif i in cache and j in cache[i]:
return cache[i][j]
else:
cache[i][j] = self.helper(i+1,j, M, N, grid, cache) + self.helper(i,j+1, M, N, grid, cache)
return cache[i][j]
return 0
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
cache = defaultdict(dict)
M, N = len(obstacleGrid), len(obstacleGrid[0])
return self.helper(0, 0, M, N, obstacleGrid, cache)
```

**Dynamic Programming**

```
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
MM = obstacleGrid
N = len(MM)
M = len(MM[0])
if M == 0:
return 1
dp = [0]*M
dp[0] = abs(MM[0][0]-1)
for j in range(1, M):
dp[j] = dp[j-1]*abs(MM[0][j]-1)
for i in range(1, N):
temp = [0]*M
temp[0] = dp[0]*abs(MM[i][0]-1)
for j in range(1, M):
temp[j] = dp[j]*abs(MM[i][j]-1) + temp[j-1]*abs(MM[i][j]-1)
dp = temp
return dp[M-1]
```