# LeetCode: Unique Paths II

## Solution: DFS with memorization

Note: we can only move with the direction of right or down. y), the way to (x, y) = (x-1, y) + (x, y-1), under the condition of [x-1, y] or [x, y-1] is not obstacle grid.

So we could use a DFS to calculate the number of paths, memorization will reduce much of duplicated computation.

`````` class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
ans = 0;
row = obstacleGrid.size();
if(row == 0) return 0;
col = obstacleGrid[0].size();
dp = vector<vector<int>>(row, vector<int>(col, -1));
if(obstacleGrid[0][0] == 1 || obstacleGrid[row-1][col-1] == 1) return 0;
return dfs(obstacleGrid, row-1, col-1);
}

int dfs(vector<vector<int>>& obstacleGrid, int x, int y) {
if(dp[x][y] != -1) return dp[x][y];
if(x == 0 && y == 0) return 1;
int cnt = 0;
if(y-1 >= 0 && obstacleGrid[x][y-1] != 1) // if down is possible
cnt += dfs(obstacleGrid, x, y-1);
if(x-1 >= 0 && obstacleGrid[x-1][y] != 1) // if right is possible
cnt += dfs(obstacleGrid, x-1, y);
dp[x][y] = cnt;
return cnt;
}

int ans;
int row;
int col;
vector<vector<int>> dp;
};
``````
Last Updated on