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 as1and0respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0]]
The total number of unique paths is2.
Note:mandnwill be at most 100.
加上障碍物后就不能像前面那样直接使用排列组合的知识求解了。这样就只能使用动态规划了，障碍物的含义可以这么理解，就是能到达有障碍物的那些网格的步数为0，这样是否有无障碍物就可以统一起来了。对于网格中的一个点，只有当它那一点无障碍物时，才等于左边网格和上边网格的值，否则保持它的默认值。
上一次是使用动态数组，这一次使用vector来实现。
runtime:4ms
class Solution {public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int width=obstacleGrid[0].size();int height=obstacleGrid.size();vector<vector<int>> mask;//这种写法是声明一个空的vectorfor(int i=0;i<height+1;i++){vector<int> tmp(width+1);//这种写法会使tmp默认大小为width+1，，并将每一个元素初始为0mask.push_back(tmp);}for(int i=0;i<height;i++){for(int j=0;j<width;j++){if(i==0&&j==0){//只有这一点没有障碍物才更新，否则保持默认值0if(obstacleGrid[i][j]==0)mask[i+1][j+1]=1;}else{//只有这一点没有障碍物才更新，否则保持默认值if(obstacleGrid[i][j]==0){mask[i+1][j+1]=mask[i+1][j]+mask[i][j+1];}}}}return mask[height][width];}};
向上攀爬的。
