DP, Time = O(n^2), Space = O(1)
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid[0][0] == 1) {
obstacleGrid[0][0] = 0;
} else {
obstacleGrid[0][0] = 1;
}
for (int i = 1; i < obstacleGrid.length; i++) {
if (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) {
obstacleGrid[i][0] = 1;
} else {
obstacleGrid[i][0] = 0;
}
}
for (int j = 1; j < obstacleGrid[0].length; j++) {
if (obstacleGrid[0][j] == 0 && obstacleGrid[0][j - 1] == 1) {
obstacleGrid[0][j] = 1;
} else {
obstacleGrid[0][j] = 0;
}
}
for (int i = 1; i < obstacleGrid.length; i++) {
for (int j = 1; j < obstacleGrid[0].length; j++) {
if (obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
} else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
}
}