算法练习（15） —— Unique Paths II
习题
本题取自 leetcode 中的 Dynamic Programming 栏目中的第63题：
Unique Paths II
题目如下：
Description
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.
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 ，具体可看算法练习（14）
- II 与 I 主要的不同是其中添加了障碍物。添加了障碍物之后，就没办法这么简单的计算了。毕竟如果原本没有障碍物，长为m，宽为n，甚至可以简单地用排列组合算出：C(n-1)[(m-1)*(n-1)]
- 增加了障碍物之后，就必须考虑几种情况：
- 自身所在地点为障碍物 ： 将本地点设为0，因为不能通过，所以独立的通路数肯定也为0。这个无论障碍是在边界还是非边界都适用
- 自身的上方或左方有一个有障碍物 ： 自身取非障碍物那个点的通路数
- 自身的上、左方都是障碍物 ： 自身设为0。因为左和上都走不通的话，就不存在通过本点的路径
- 自身的上、左方都没有障碍物 ： 做法同练习（14）即可
代码如下：
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int h = obstacleGrid.size();int w = obstacleGrid[0].size();if(h == 0 || w == 0 || obstacleGrid[0][0])return 0;obstacleGrid[0][0] = 1;// initializefor(int i = 1; i < w; i++)obstacleGrid[0][i] = obstacleGrid[0][i] ? 0 : obstacleGrid[0][i - 1];for(int j = 1; j < h; j++) {obstacleGrid[j][0] = obstacleGrid[j][0] ? 0 : obstacleGrid[j - 1][0];for(int i = 1; i < w; i++) {obstacleGrid[j][i] = obstacleGrid[j][i] ? 0 : obstacleGrid[j - 1][i] + obstacleGrid[j][i - 1];}}return obstacleGrid[h - 1][w - 1];}
};