## 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 3×3 grid as illustrated below.

[ [0,0,0], [0,1,0], [0,0,0] ]The total number of unique paths is

`2`

.

Note:mandnwill be at most 100.

和Unique Paths I很像。

转移方程变一下即可，如果obstacleGrid[i][j] == 1 ，map[i][j] = 0;

否则 map[i][j] = map[i-1][j] + map[i][j-1];

这里需要注意数组的初始化。

int map[2][2] = {0};不能将所有元素初始化，需要一个循环来初始化。

class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { if(obstacleGrid.empty()) return 0; int height = obstacleGrid.size(); int length = obstacleGrid[0].size(); if(height == 0 || length == 0) return 0; int map[height + 1][length + 1]; for(int i = 0; i < height + 1; i++){ for(int j = 0; j < length + 1; j++){ map[i][j] = 0; } } for(int i = 1; i <= height; i++){ for(int j = 1; j <= length; j++){ if(obstacleGrid[i - 1][j - 1] == 1){ map[i][j] = 0; } else if(i == 1 && j == 1){ map[i][j] = 1; } else{ map[i][j] = map[i-1][j] + map[i][j-1]; } } } return map[height][length]; } };