63. Unique Paths II

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