C++ DP 3ms O(n) Space

• ``````class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
// parameters check
if (obstacleGrid.empty() || obstacleGrid[0].empty()) {
return 0;
}
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
// keep the number of unique paths for the first line.
vector<int> path(n, 1);
// initialize the first line path, when obstacle is encounterred, assign 0 to all the rest elements.
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 1) {
while (i < n) {
path[i++] = 0;
}
}
}
// start from the second line. for each line, check if the first is obstacle, if it is, then set path[0] = 0 which means no path going down from now on.
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0) {
if (obstacleGrid[i][0] == 1) {
path[0] = 0;
}
continue;
}
if (obstacleGrid[i][j] == 1) {
path[j] = 0;
} else {
path[j] = path[j] + path[j - 1];
}
}
}
return path[n - 1];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.