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.
简单动态规划，注意特殊情况，即第一个元素为1.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 |
class
Solution {public: int
uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { vector<int> p(obstacleGrid.size(),0); if(obstacleGrid[0][0] == 1)return
0; p[0] = 1; for(int
i = 1 ; i <obstacleGrid.size();i++) if(obstacleGrid[i][0] == 0&&p[i-1] == 1) p[i] = 1; else
p[i] = 0 ; for(int
i = 1 ; i <obstacleGrid[0].size();i++) { if(obstacleGrid[0][i] == 1) p[0] = 0; for(int
j = 1 ; j < obstacleGrid.size();j++) { if(obstacleGrid[j][i] == 1)p[j] = 0; else
p[j] += p[j-1]; } } return
p[obstacleGrid.size()-1]; }}; |
Unique Paths II,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3595774.html