# Java dp solutions (O(n*n), O(n) space).

• ``````// O(n*n) space
public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
int row = obstacleGrid.length, col = obstacleGrid[0].length;
int dp[][] = new int[row][col];
dp[0][0] = 1-obstacleGrid[0][0];
for (int i=1; i<row; i++)
dp[i][0] = dp[i-1][0]*(1-obstacleGrid[i][0]);
for (int j=1; j<col; j++)
dp[0][j] = dp[0][j-1]*(1-obstacleGrid[0][j]);
for (int i=1; i<row; i++)
for (int j=1; j<col; j++)
dp[i][j] = (dp[i-1][j]+dp[i][j-1])*(1-obstacleGrid[i][j]);
return dp[row-1][col-1];
}

// O(n) space
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int row = obstacleGrid.length, col = obstacleGrid[0].length;
int dp[] = new int[col];
dp[0] = 1-obstacleGrid[0][0];
for (int j=1; j<col; j++)
dp[j] = dp[j-1]*(1-obstacleGrid[0][j]);
for (int i=1; i<row; i++) {
dp[0] *= 1-obstacleGrid[i][0];
for (int j=1; j<col; j++)
dp[j] = (dp[j-1]+dp[j])*(1-obstacleGrid[i][j]);
}
return dp[col-1];
}``````

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