1. dp
类似[62. 不同路径]，只是在遇到障碍时清零dp即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<int> dp(n, 0);
dp[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
continue;
}
if (j > 0)
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
};
|