Space optimised dp solution


#1
int paths(vector<vector<int> > &A){

int row = A.size();
if(row==0) return 0;
int col = A[0].size();
vector<int> prev(row);
vector<int> curr(row);
if(A[0][0]==1) return 0;
prev[0]=1;
for(int i=1;i<row;i++){
    if(A[i][0]==1) prev[i]=0;
    else prev[i]=prev[i-1];
}
if(col==1) return prev[row-1];

for(int c = 1; c<col ; c++){
    if(A[0][c]==1) curr[0]=0;
    else curr[0]=prev[0];
    for(int i=1; i<row ; i++){
        if(A[i][c]==1) curr[i]=0;
        else curr[i]=prev[i]+curr[i-1];
    }
    prev=curr;
}
return curr[row-1];

}

int Solution::uniquePathsWithObstacles(vector<vector > &A) {
return paths(A);
}