dp O(mn) time O(mn) space
相比unique paths只需要多考虑如果是障碍的时候直接为0即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int n = obstacleGrid.size();
if (n < 1) return 0;
int m = obstacleGrid[0].size();
if (m < 1) return 0;
if (obstacleGrid[0][0] || obstacleGrid[n - 1][m - 1]) return 0;
vector<vector<int>> f(n + 1, vector<int>(m + 1));
f[0][1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
f[i][j] = obstacleGrid[i - 1][j - 1] ? 0 : f[i - 1][j] + f[i][j - 1];
}
}
return f[n][m];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
vector<vector<int> > ret(obstacleGrid.size() + 1, vector<int>(obstacleGrid.front().size() + 1));
ret[0][1] = 1;
for (int row(1); row < ret.size(); ++row)
for (int col(1); col < ret[row].size(); ++col)
if (!obstacleGrid[row - 1][col - 1])
ret[row][col] = ret[row - 1][col] + ret[row][col - 1];
return ret.back().back();
}
};
|