# LeetCode题目：Unique Paths II，二维动态规划

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: m and n will be at most 100.

```class Solution {
public:
int uniquePathsWithObstacles(vector > &obstacleGrid) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = obstacleGrid.size();
if(rows == 0) return 0;
int cols = obstacleGrid[0].size();
if(cols == 0) return 0;
int *preways = new int[cols];
int *ways = new int[cols];

//first row
preways[0] = 1 - obstacleGrid[0][0];
for(int i = 1; i  &rowobs = obstacleGrid[ir];
for(int ic = 0; ic < cols; ++ic) {
if(rowobs[ic] == 1) {
ways[ic] = 0;
continue;
}
//from cell above
ways[ic] = preways[ic];
//from left
if(ic > 0) {
ways[ic] += ways[ic - 1];
}
}
int *temp = preways;
preways = ways;
ways = temp;
}
return preways[cols-1];
}
};
```