Lintcode：不同的路径Ⅱ

问题：

"不同的路径" 的跟进问题：

现在考虑网格中有障碍物，那样将会有多少条不同的路径？

网格中的障碍和空位置分别用 1 和 0 来表示。

样例：

Example 1: Input: [[0]] Output: 1 Example 2: Input: [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: Only 2 different path.

注意事项

m 和 n 均不超过100

python：

class Solution: """ @param obstacleGrid: A list of lists of integers @return: An integer """ def uniquePathsWithObstacles(self, obstacleGrid): # write your code here m = len(obstacleGrid) n = len(obstacleGrid[0]) nums = [[0 for i in range(n)] for j in range(m)] if obstacleGrid[0][0] == 1: return 0 for i in range(m): if obstacleGrid[i][0] == 0: nums[i][0] = 1 else: break for j in range(n): if obstacleGrid[0][j] == 0: nums[0][j] = 1 else: break for i in range(1,m): for j in range(1,n): if obstacleGrid[i][j] == 0: nums[i][j] = nums[i-1][j] + nums[i][j-1] else: nums[i][j] = 0 return nums[m-1][n-1]

C++：

class Solution { public: /** * @param obstacleGrid: A list of lists of integers * @return: An integer */ int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) { // write your code here int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int>> nums(m,vector<int>(n)); if(obstacleGrid[0][0] == 1) { return 0; } for(int i = 0; i < m; i++) { if(obstacleGrid[i][0] == 0) { nums[i][0] = 1; }else{ break; } } for(int j = 0; j < n; j++) { if(obstacleGrid[0][j] == 0) { nums[0][j] = 1; }else{ break; } } for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { if(obstacleGrid[i][j] == 0) { nums[i][j] = nums[i-1][j] + nums[i][j-1]; }else{ nums[i][j] = 0; } } } return nums[m-1][n-1]; } };