Cpp solution simple


#1

int Solution::uniquePathsWithObstacles(vector<vector > &v) {
int i,j,n=v.size(),m=v[0].size();
vector<vector > ans(n,vector(m));
if(v[n-1][m-1]==1)
return 0;
ans[n-1][m-1]=1;
for(i=n-1;i>=0;i–){
for(j=m-1;j>=0;j–){
if(i==n-1&&j==m-1)
continue;
else if(i==n-1)
ans[i][j]=v[i][j]==0?ans[i][j+1]:0;
else if(j==m-1)
ans[i][j]=v[i][j]==0?ans[i+1][j]:0;
else
ans[i][j]=v[i][j]==0?ans[i+1][j]+ans[i][j+1]:0;
}
}
return ans[0][0];
}


#2

easy to understand cpp O(mn) time, O(mn) space

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