# DP using C++(4ms)

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

if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)  return 0;

int **dp = new int*[m+1];
for(int i = 0; i <= m; i ++){
dp[i] = new int[n+1];
}

for(int i = 0; i <= m; i ++) dp[i][0] = 0;
for(int j = 0; j <= n; j ++) dp[0][j] = 0;

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

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

for(int i = 2; i <= m; i ++){
for(int j = 2; j <= n; j ++){
if(obstacleGrid[i-1][j-1] == 1) dp[i][j] = 0;
else{
dp[i][j] = (obstacleGrid[i-2][j-1] == 1 ? 0 : dp[i-1][j]) +
(obstacleGrid[i-1][j-2] == 1 ? 0 : dp[i][j-1]);
}
}
}

int res = dp[m][n];
for(int i = 0; i <= m; i ++){
delete [] dp[i];
}

delete [] dp;

return res;
}
``````

};

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