# My C++ Dp solution , very simple!

• just use dp to find the answer , if there is a obstacle at (i,j), then dp[i][j] = 0.
time is O(nm) , space is O(nm) .
here is my code:

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

• You don't need extra space .

• elegant code! could you explain why it is "if(!obstacleGrid[i-1][j-1])" but not "if(!obstacleGrid[i][j])"

• Here is my solution using O(n) space :)

``````class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1)
return 0;

int res[n];
res[n-1] = 1;
for(int i = n-2; i >= 0; --i){
if(obstacleGrid[m-1][i] == 1)
res[i] = 0;
else
res[i] = res[i+1];
}

for(int i = m-2; i >= 0; --i){
for(int j = n-1; j >=0; --j){
if(j == n-1){
if(obstacleGrid[i][j] == 1)
res[j] = 0;
}else{
if(obstacleGrid[i][j] == 1)
res[j] = 0;
else
res[j] += res[j+1];
}
}
}
return res[0];
}
};``````

• because obstacleGrid size is m*n, but dp is (m+1) * (n+1)

• ``````class Solution {
``````

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

``````    int row=obstacleGrid.size();
int col=obstacleGrid[0].size();
vector<vector<int>> k(row,vector<int>(col,0));

if(obstacleGrid[0][0]==1||obstacleGrid[row-1][col-1]==1)
return 0;
else
k[0][0]=1;

for(int i=1;i<row;++i)
if(!obstacleGrid[i][0])
k[i][0]=k[i-1][0];

for(int j=1;j<col;++j)
if(!obstacleGrid[0][j])
k[0][j]=k[0][j-1];

for(int i=1;i<row;++i)
for(int j=1;j<col;++j)
{
if(!obstacleGrid[i][j])
k[i][j]=k[i-1][j]+k[i][j-1];

}
return k[row-1][col-1];

}
``````

};

• Nice pre-processing `dp[0][1] = 1;` to make the code so simple!

• But why did u make it one??

• Your have to initialise the entry point for the first time.(your for loop is begin with(1,1))

• Without extra space: (I can combine all three loop into one, but I don't wanna have too much condition checking.)

``````public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;

//flip upper left cell (the start cell): 1 => 0 or 0 => 1
obstacleGrid[0][0] ^= 1;

//first row: if 1, then 0; otherwise, left cell
for(int i = 1; i < n; i++)
obstacleGrid[0][i] = obstacleGrid[0][i] == 1 ? 0 : obstacleGrid[0][i - 1];

//first column: if 1, then 0; otherwise, top cell
for(int i = 1; i < m; i++)
obstacleGrid[i][0] = obstacleGrid[i][0] == 1 ? 0 : obstacleGrid[i - 1][0];

//rest: if 1, then 0; otherwise, left cell + top cell
for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++)
obstacleGrid[i][j] = obstacleGrid[i][j] == 1 ? 0 : obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];

//return lower right cell (the end cell)
return obstacleGrid[m - 1][n - 1];
}
}``````

• This post is deleted!

• More concise and O(n) space:

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

• ``````    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
vector<int> dp(n+1,0);
dp[1]=1;
for(int i=0;i<m;i++){
for(int j=1;j<=n;j++){
if(obstacleGrid[i][j-1]) dp[j]=0;
else dp[j]=dp[j]+dp[j-1];
}
}
return dp[n];
}
``````

• @SpicyDog But you changed argument.Argument original is referenced parameter.

• i used it, but got run-time error when submit, can anyone help me?
here is code

``````    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size() , n = obstacleGrid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
dp[0][1] = 1;
for(int i = 1 ; i <= m ; ++i)
for(int j = 1 ; j <= n ; ++j)
if(!obstacleGrid[i-1][j-1])
dp[i][j] = dp[i-1][j]+dp[i][j-1];
return dp[m][n];
}``````

• @sutongkui i got it, use long int instead of int

They've just updated their C++ compiler settings to detect integer overflow(which would usually be just ignored and wrapped around).

So the runtime error is caused by integer overflow.
Reference:
http://en.cppreference.com/w/cpp/error/overflow_error

• @sutongkui
you'd better add the {} for every for loop and if statement.

• @uestc-ym becasue the element in obstacleGrid with index of[i-1,j-1] map to the dp's[i,j]
NOTICE: vector's index starts from 0.

• ``````class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
vector<int>v(obstacleGrid[0].size(),0);
for(int i = 0 ; i < obstacleGrid[0].size() ; ++i){
if( obstacleGrid[0][i] == 1 )break;
v[i] = 1;
}
for(int i = 1 ; i < obstacleGrid.size() ; ++i){
for(int j = 0 ; j < obstacleGrid[0].size() ; ++j){
if( obstacleGrid[i][j] == 1 )
v[j] = 0;
else v[j] = (j == 0) ?  v[j] : v[j] + v[j-1];
}
}
return v[v.size()-1];
}
};
``````

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