Unique easy C++ soln using dp


#1

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