首页 > 代码库 > [Leetcode] Unique Paths II
[Leetcode] 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.
Note: m and n will be at most 100.
Solution：dp
1 public class Solution { 2 public int uniquePathsWithObstacles(int[][] obstacleGrid) { 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 if(obstacleGrid[i][0]==1){ 9 dp[i][0]=0;10 break;11 }else{12 dp[i][0]=1;13 }14 15 }16 for(int i=0;i<N;++i){17 if(obstacleGrid[0][i]==1){18 dp[0][i]=0;19 break;20 }else{21 dp[0][i]=1;22 }23 }24 25 for(int i=1;i<M;++i){26 for(int j=1;j<N;++j){27 if(obstacleGrid[i][j]==1){28 dp[i][j]=0;29 }else{30 dp[i][j]=dp[i-1][j]+dp[i][j-1];31 }32 }33 }34 35 return dp[M-1][N-1];36 }37 }
以下为大神的代码：https://github.com/mengli/leetcode/blob/master/UniquePathsII.java
1 public class UniquePathsII { 2 public int uniquePathsWithObstacles(int[][] obstacleGrid) { 3 int m = obstacleGrid.length; 4 if (m == 0) 5 return 0; 6 int n = obstacleGrid[0].length; 7 int[][] map = new int[m][n]; 8 map[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1; 9 for (int i = 1; i < m; i++) {10 map[i][0] = obstacleGrid[i][0] == 1 ? 0 : map[i - 1][0];11 }12 for (int j = 1; j < n; j++) {13 map[0][j] = obstacleGrid[0][j] == 1 ? 0 : map[0][j - 1];14 }15 for (int i = 1; i < m; i++) {16 for (int j = 1; j < n; j++) {17 map[i][j] = obstacleGrid[i][j] == 1 ? 0 : map[i - 1][j]18 + map[i][j - 1];19 }20 }21 return map[m - 1][n - 1];22 }23 }
[Leetcode] Unique Paths II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。