给定一个矩阵，矩阵元素由0/1组成，0表示可以通过，1表示有障碍，不能通过，且每次只能向右走或者向下走，求从矩阵左上角走到矩阵右下角的路线条数。
Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
思路：
此题跟62题“Unique Paths”基本一模一样，除了增加了一些障碍，其余都一样。解题思路也和62题一样，需要注意的点在于，在初始化的时候，要看 dp[k][0]和dp[0][k]上面有没有障碍，如果有障碍，则表示通不过，值设为0，如果没有障碍，值设为1。用haveObstacle 表示是否有障碍即可。后续的遍历，遇到原矩阵元素值为1，则dp[i][j] = 0; 否则 dp[i][j] = dp[i-1][j] + dp[i][j-1].
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int n = obstacleGrid.size(), m = obstacleGrid[0].size(); vector<vector<int>> dp(n, vector<int>(m)); bool haveObstacle = false; for (int k = 0; k < m; k++) { if (obstacleGrid[0][k] == 1) haveObstacle = true; dp[0][k] = haveObstacle ? 0 : 1; } haveObstacle = false; for (int k = 0; k < n; k++) { if (obstacleGrid[k][0] == 1) haveObstacle = true; dp[k][0] = haveObstacle ? 0 : 1; } for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (obstacleGrid[i][j] == 1) dp[i][j] = 0; else dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[n - 1][m - 1]; } };
原文：https://www.cnblogs.com/luo-c/p/13019630.html