?
Unique Paths II
?
来自 <https://leetcode.com/problems/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.
?
题目解读：
?
上接题目“Unique Paths”
?
现在考虑如果某个方格内添加上障碍物，那一共有多少种唯一路径？在数组中的障碍物和空白分别用1和0表示。
?
例如：
?
在一个3*3的方格中，有一个障碍物，表示如下
?
[
? [0,0,0],
? [0,1,0],
? [0,0,0]
]
?
总共的唯一路径数为2.
?
注：m 和n的最大值为100.
?
解析：
?
这个题和Unique Paths一样，都属于动态规划的问题，但此问题中添加了障碍物，到达障碍物下端down或右端right的路径数为down左端的路径数和right上端的路径数。如果把障碍物所在的数组元素值设为0，则就能变成河unique paths的问题相同。
?
Java代码：
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//行数
int rows = obstacleGrid.length;
//列数
int cols = obstacleGrid[0].length;
//如果起始位置被堵死，则没有到达目的地的路径
if(obstacleGrid[0][0]==1)
return 0;
int value = 1;
for(int i=0; i<cols; i++) {
if(obstacleGrid[0][i] == 1)
value = 0;
obstacleGrid[0][i] = value;
}
//如果第一行或第一列的某个数组元素为1，则到达其后续的行和列中的路径为0种
value =1;
for(int i=1; i<rows; i++) {
if(obstacleGrid[i][0] == 1)
value = 0;
obstacleGrid[i][0] = value;
}
//到达空格i,j的路径等于到达其上方和其左方路径之和
for(int i=1; i<rows; i++) {
for(int j=1; j<cols; j++) {
if(obstacleGrid[i][j] != 1)
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
else
obstacleGrid[i][j]=0;
}
}
return obstacleGrid[rows-1][cols-1];
}
}
?
算法性能：
?
?
?
原文：http://972459637-qq-com.iteye.com/blog/2243177