63.UniquePaths II---dp

题目大意：与62题类似，只是这个题中间有障碍。

法一：dfs，依旧超时。代码如下：

 1     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 2         boolean vis[][] = new boolean[obstacleGrid.length][obstacleGrid[0].length];
 3         int f[][] = {{1, 0}, {0, 1}};
 4         //如果起始格子就是障碍，则表示不能正常到达目的地
 5         if(obstacleGrid[0][0] == 1) {
 6             return 0;
 7         }
 8         return dfs(obstacleGrid, 0, 0, 0, f, vis);
 9     }
10     public static int dfs(int[][] obstacleGrid, int x, int y, int cnt, int f[][], boolean vis[][]) {
11         if(x == obstacleGrid.length - 1 && y == obstacleGrid[0].length - 1 && obstacleGrid[x][y] == 0) {
12             cnt++;
13             return cnt;
14         }
15         for(int i = 0; i < 2; i++) {
16             int cnt_x = x + f[i][0];
17             int cnt_y = y + f[i][1];
18             if(cnt_x < obstacleGrid.length && cnt_y < obstacleGrid[0].length && vis[cnt_x][cnt_y] == false && obstacleGrid[cnt_x][cnt_y] == 0) {
19                 vis[cnt_x][cnt_y] = true;
20                 cnt = dfs(obstacleGrid, cnt_x, cnt_y, cnt, f, vis);
21                 vis[cnt_x][cnt_y] = false;
22             } 
23         }
24         return cnt;
25     }

View Code

法二：dp，模仿62题的dp，只是这里要考虑障碍。代码如下（耗时2ms）：

 1     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 2         //如果起始位置或结束位置是1，则直接不通
 3         if(obstacleGrid[0][0] == 1 || obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
 4             return 0;
 5         }
 6         int dp[][] = new int[obstacleGrid.length][obstacleGrid[0].length];
 7         //初始化第一列
 8         for(int i = 0; i < obstacleGrid.length; i++) {
 9             if(obstacleGrid[i][0] == 0) {
10                 dp[i][0] = 1;
11             }
12             else {//第一列，一旦碰到一个障碍1，则第一列障碍下面的所有都是障碍，不通
13                 for(; i < obstacleGrid.length; i++) {
14                     dp[i][0] = 0;
15                 }
16                 break;
17             }
18         }
19         //初始化第一行
20         for(int i = 0; i < obstacleGrid[0].length; i++) {
21             if(obstacleGrid[0][i] == 0) {
22                 dp[0][i] = 1;
23             }
24             else {//第一行，一旦碰到一个障碍1，则第一行障碍后面的所有都是障碍，不通
25                 for(; i < obstacleGrid[0].length; i++) {
26                     dp[0][i] = 0;
27                 }
28                 break;
29             }
30         }
31         //计算dp
32         for(int i = 1; i < obstacleGrid.length; i++) {
33             for(int j = 1; j < obstacleGrid[0].length; j++) {
34                 if(obstacleGrid[i][j] == 1) {//如果当前格是障碍，则不可通
35                     dp[i][j] = 0;
36                 }
37                 else {
38                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
39                 }
40             }
41         }
42         return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
43     }

View Code

法三：一维dp，与62题很类似，但是要比62题难思考一点，因为要考虑障碍的问题，而且没有初始化，直接从0开始遍历的。代码如下（耗时1ms）：

 1     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 2         if(obstacleGrid[0][0] == 1 || obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
 3             return 0;
 4         }
 5         int[] dp = new int[obstacleGrid[0].length];
 6         dp[0] = 1;
 7         //从0开始遍历，否则会漏掉第一列，因为其实第一列并没有初始化
 8         for(int i = 0; i < obstacleGrid.length; i++) {
 9             for(int j = 0; j < obstacleGrid[0].length; j++) {
10                 //遇到障碍则赋0
11                 if(obstacleGrid[i][j] == 1) {
12                     dp[j] = 0;
13                 }
14                 //由于j是从0开始，所以只考虑>0的情况
15                 else if(j > 0){
16                     dp[j] += dp[j - 1];
17                 }
18             }
19         }
20         return dp[obstacleGrid[0].length - 1];
21     }

View Code