题目：
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0]]
The total number of unique paths is 2.
Note: m and n will be at most 100.
链接：
题解：
也是DP问题，Unique Path一样可以in place解决。要点是在设置第一行和第一列碰到obstacle的时候，要将其以及之后的所有值设置为零，因为没有路径可以达到。之后在DP扫描矩阵的时候，也要讲obstacle所在的位置清零。
Time Complexity - O(m * n)， Space Complexity - O(1)。
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int rowNum = obstacleGrid.length, colNum = obstacleGrid[0].length; if(obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0][0] == 1){ return 0; } for(int row = 0; row < rowNum; row ++){ if(obstacleGrid[row][0] == 0) obstacleGrid[row][0] = 1; else if (obstacleGrid[row][0] == 1){ //if find obstacle, set all [row,0] below obstacle to 0 for(int tempRow = row; tempRow < rowNum; tempRow ++) obstacleGrid[tempRow][0] = 0; break; } } for(int col = 1; col < colNum; col ++){ if(obstacleGrid[0][col] == 0) obstacleGrid[0][col] = 1; else if (obstacleGrid[0][col] == 1){ // //if find obstacle, set all [0,col] one the right of obstacle to 0 for(int tempCol = col; tempCol < colNum; tempCol ++) obstacleGrid[0][tempCol] = 0; break; } } for(int i = 1; i < rowNum; i ++){ for(int j = 1; j < colNum; j ++){ if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0; else obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]; } } return obstacleGrid[rowNum - 1][colNum - 1]; }}
二刷：
和一刷一样， 就是先判断行和列中的obstacle元素，将其与其之后的为止置零。接下来遍历整个矩阵。
Java:
Time Complexity - O(m * n)， Space Complexity - O(1)。
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0][0] == 1) { return 0; } int rowNum = obstacleGrid.length, colNum = obstacleGrid[0].length; for (int i = 0; i < rowNum; i++) { if (obstacleGrid[i][0] == 1) { for (int k = i; k < rowNum; k++) { obstacleGrid[k][0] = 0; } break; } else { obstacleGrid[i][0] = 1; } } for (int j = 1; j < colNum; j++) { if (obstacleGrid[0][j] == 1) { for (int k = j; k < colNum; k++) { obstacleGrid[0][k] = 0; } break; } else { obstacleGrid[0][j] = 1; } } for (int i = 1; i < rowNum; i++) { for (int j = 1; j < colNum; j++) { if (obstacleGrid[i][j] == 1) { obstacleGrid[i][j] = 0; } else { obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]; } } } return obstacleGrid[rowNum - 1][colNum - 1]; }}
三刷:
Java:
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0][0] == 1) { return 0; } int rowNum = obstacleGrid.length, colNum = obstacleGrid[0].length; for (int i = 0; i < rowNum; i++) { if (obstacleGrid[i][0] == 1) { for (int k = i; k < rowNum; k++) { obstacleGrid[k][0] = 0; } break; } else { obstacleGrid[i][0] = 1; } } for (int j = 1; j < colNum; j++) { if (obstacleGrid[0][j] == 1) { for (int k = j; k < colNum; k++) { obstacleGrid[0][k] = 0; } break; } else { obstacleGrid[0][j] = 1; } } for (int i = 1; i < rowNum; i++) { for (int j = 1; j < colNum; j++) { obstacleGrid[i][j] = obstacleGrid[i][j] == 1 ? 0 : obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]; } } return obstacleGrid[rowNum - 1][colNum - 1]; }}