# DP solution with O(N) space, without extra bounds check

• ``````class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m(obstacleGrid.size()), n(obstacleGrid[0].size());
vector<int> DP(n, 0);
DP[0] = obstacleGrid[0][0] ? 0 : 1;
for(int i(0); i < m; ++i)
{
DP[0] &= !obstacleGrid[i][0];
for(int j(1); j < n; ++j)
{
DP[j] = obstacleGrid[i][j] ? 0 : DP[j - 1] + DP[j];
}
}
return DP.back();
}
};
``````

For fist column,

0 0 0 1 0 0 1 0 ...

When meet first '1', the place after this '1' can be seems as obstacle:

0 0 0 1 1 1 1 1 ...

To avoid checking DP[0] = DP[0] + DP[0 - 1], using the code below to compute DP[0]:

``DP[0] &= !obstacleGrid[i][0];``

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