LeetCode 63. Unique Paths II

63. Unique Paths II（不同路径 II）

题目：

　　一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

　　机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记　　为“Finish”）。

　　现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

　　网格中的障碍物和空位置分别用 1 和 0 来表示。

　　说明：m 和 n 的值均不超过 100。

　　示例 1:

　　输入:
　　[
　　  [0,0,0],
　　  [0,1,0],
　　  [0,0,0]
　　]
　　输出: 2
　　解释:
　　3x3 网格的正中间有一个障碍物。
　　从左上角到右下角一共有 2 条不同的路径：
　　1. 向右 -> 向右 -> 向下 -> 向下
　　2. 向下 -> 向下 -> 向右 -> 向右

思路：

　　这题和上一题相似，区别在于存在阻碍无法通过，所以不能直接求公式，那么就采用dp算法，建立一个相同大小的数组，存放到达当前格子的路径数量。如果当前格子存在阻碍，那么就始终无法到达，设置为0，如果在第一行或者第一列，如果之前无阻碍就为1（只能通过直线到达），有阻碍就为0。中间的格子也是，有阻碍就为0，没阻碍就是上方格子和左侧格子的和，最后一个格子就是所需的路径数目。

　　本来我是把第一行第一列提出来先进行运算的，但是这样有点浪费时间，就把这些都放在一起了，好像快了一点点。

（上一题：不同路径https://www.cnblogs.com/blogxjc/p/10922799.html）

代码：

 1 public int uniquePathsWithObstacles(int[][] obstacleGrid)  
 2     {
 3         int m = obstacleGrid.length;
 4         int n = obstacleGrid[0].length;
 5         int[][] dp = new int[m][n];    
 6         
 7         for (int i = 0; i < m; i++) 
 8         {
 9             for (int j = 0; j < n; j++) 
10             {
11                 if(obstacleGrid[i][j]==1)
12                     dp[i][j] = 0;
13                 else if (i == 0 && j == 0) 
14                     dp[i][j] = 1;
15                 else if (i == 0 && j != 0)
16                     dp[i][j] = dp[i][j-1];
17                 else if (j ==0 && i != 0)
18                     dp[i][j] = dp[i-1][j];
19                 else
20                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
21             }
22         }
23         return dp[m - 1][n - 1];        
24     }

View Code