**Description:**

https://leetcode.com/problems/unique-paths-ii/#/description

**Algorithm:**

check obstacle:

- obstacle = 1 dp[i][j] = 0
- obstacle = 0 dp[i][j] = dp[i – 1][j] + dp[i][j – 1]

**Code:**

class Solution {

public:

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

int m = obstacleGrid.size();

int n = obstacleGrid[0].size();

vector<vector<int>> dp = vector<vector<int>>(m, vector<int>(n, 1));

dp[0][0] = (1 - obstacleGrid[0][0]);

for (int i = 1; i < m; i++)

dp[i][0] = (1 - obstacleGrid[i][0]) * dp[i - 1][0];

for (int i = 1; i < n; i++)

dp[0][i] = (1 - obstacleGrid[0][i]) * dp[0][i - 1];

for (int i = 1; i < m; i++)

{

for (int j = 1; j < n; j++)

{

dp[i][j] = (1 - obstacleGrid[i][j]) * (dp[i - 1][j] + dp[i][j - 1]);

}

}

return dp[m - 1][n - 1];

}

};

**Timing:**

best, 3ms