63 不同路径II
深搜(超时)
class Solution {
private:
int dfs(vector<vector<int>>& obstacleGrid, int i, int j){
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
// obstacleGrid[i][j] == 1直接返回0
if(i >= m || j >= n || obstacleGrid[i][j] == 1) return 0;
if(i == m - 1 && j == n - 1 && obstacleGrid[i][j] == 0) return 1;
return dfs(obstacleGrid, i + 1, j) + dfs(obstacleGrid, i, j + 1);
}
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
return dfs(obstacleGrid,0, 0);
}
};
动态规划
初始化的时候注意
obstacleGrid[i][0] == 0说明dp[i + 1][0] == 0及之后的dp[i][0]都为0
二维做法
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 0)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
else
dp[i][j] = 0;
}
}
return dp[m - 1][n - 1];
}
};
一维优化
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<int> dp(n, 0);
// 这里不仅把dp[0][j]都初始化为1
// 而且把dp[i][0](i == 0)初始化为1
// 在之后的循环中,如果obstacleGrid[i][0] == 0那么dp[i][0]将一直保持为1
for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[j] = 1;
for(int i = 1; i < m; i++){
// 这里必须从j == 0开始
// 因为如果obstacleGrid[i][0] == 1,需要将dp[i][0]更改状态为0
// 一旦更改状态为0后,之后将一直保持状态为0
for(int j = 0; j < n; j++){
if(obstacleGrid[i][j] == 1)
dp[j] = 0;
else if(j != 0)
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
};