首页 > 代码库 > LintCode-Unique Path II
LintCode-Unique Path 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.
Note
m and n will be at most 100.
Example
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:
DP: d[i][j] = d[i][j-1]+d[i-1][j].
NOTE: We can use 1D array to perform the DP. Since d[i][j] depends on d[i][j-1], i.e., the new d[][j-1], we should increase j from 0 to end. If d[i][j] depends on d[i-1][j-1] then we should decrease j from end to 0.
Solution:
1 public class Solution { 2 /** 3 * @param obstacleGrid: A list of lists of integers 4 * @return: An integer 5 */ 6 public int uniquePathsWithObstacles(int[][] obstacleGrid) { 7 int rowNum = obstacleGrid.length; 8 if (rowNum==0) return 0; 9 int colNum = obstacleGrid[0].length;10 if (colNum==0) return 0;11 if (obstacleGrid[0][0]==1) return 0; 12 13 int[] path = new int[colNum];14 path[0] =1;15 for (int i=1;i<colNum;i++)16 if (obstacleGrid[0][i]==1) path[i]=0;17 else path[i] = path[i-1];18 19 for (int i=1;i<rowNum;i++){20 if (obstacleGrid[i][0]==1) path[0]=0;21 for (int j=1;j<colNum;j++)22 if (obstacleGrid[i][j]==1) path[j]=0;23 else path[j]=path[j-1]+path[j];24 25 }26 27 28 return path[colNum-1];29 }30 }
LintCode-Unique Path II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。