Unique Paths II
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.
Analysis
From problem "unique path", this is a bottom-up DP problem
- state: $$dp[i][j]$$: 从i,j到右下角的unique path数
- transfer: $$dp[i][j]=dp[i][j+1]+dp[i+1][j]$$
- initialize: all last row and last column 1
- return $$dp[0][0]$$
Different from "unique path"
- For all obstacles, dp = 0
- Initialize difference: 一旦最后一行(列)有一个obstacle的话,它的左边(上面)全部为0, 右边和下面不受影响
Code (bottom to top)
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if (obstacleGrid[m-1][n-1]==1) {return 0;}
int[][] map = new int[m][n];
//initialize last row
for(int j=n-1; j>=0; j--){
if(obstacleGrid[m-1][j]==1) {break;}
else {map[m-1][j]=1;}
}
//initialize last colomn
for(int i=m-2; i>=0;i--){
if(obstacleGrid[i][n-1]==1) {break;}
else {map[i][n-1]=1;}
}
for (int i=m-2; i>=0 ; i--){
for(int j=n-2;j >=0 ;j--){
if (obstacleGrid[i][j]==1) {map[i][j] =0;}
else {map[i][j] = map[i][j+1] + map[i+1][j]; }
}
}
return map[0][0];
}
}
Code (top to bottom)
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid==null || obstacleGrid.length==0 || obstacleGrid[0].length==0) return 0;
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i=0; i<m; i++){
if (obstacleGrid[i][0]==1) break;
else dp[i][0]=1;
}
for (int j=0; j<n; j++){
if (obstacleGrid[0][j]==1) break;
else dp[0][j]=1;
}
for (int i=1; i<m; i++){
for (int j=1; j<n; j++){
if (obstacleGrid[i][j]==1) dp[i][j]=0;
else {dp[i][j] = dp[i-1][j] + dp[i][j-1];}
}
}
return dp[m-1][n-1];
}
}