1
class Solution {
2
 public:
3
  int dp[101][101];
4
  int paths(int i, int j, int &m, int &n, vector<vector<int>> &grid) {
5
    if (i >= m || j >= n) return 0;
6

7
    if (grid[i][j] == 1) return 0;
8

9
    if (i == m - 1 && j == n - 1) return 1;
10

11
    if (dp[i][j] != -1) return dp[i][j];
12

13
    int v = paths(i, j + 1, m, n, grid);
14
    int h = paths(i + 1, j, m, n, grid);
15

16
    return dp[i][j] = v + h;
17
  }
18
  int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
19
    int m = obstacleGrid.size();
20
    int n = obstacleGrid[0].size();
21

22
    memset(dp, -1, sizeof(dp));
23

24
    return paths(0, 0, m, n, obstacleGrid);
25
  }
26
};