最近英文版的访问特别慢，转战中文吧
和上一题一样，递归会超时
//63 不同路径2,递归解法
int uniquePaths2(vector<vector<int>>& obstacleGrid, int m,int n) {
if ((m == && n == ) || (m == && n == ) || (m == && n == )) {
if (obstacleGrid[obstacleGrid.size() - ][obstacleGrid[].size() - ] == )
return ;
else
return ;
}
int p1 = ;
int p2 = ;
//获得向下走的总数,当下面的数为1或者是到了最底层,向下的总数为0
if (m == || obstacleGrid[m-][n-] == )
p1 = ;
else
p1 = uniquePaths2(obstacleGrid,m-,n);
//向右
if (n == || obstacleGrid[m - ][n - ] == )
p2 = ;
else
p2 = uniquePaths2(obstacleGrid, m, n - );
return p1 + p2;
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid[][] == )
return ;
return uniquePaths2(obstacleGrid,obstacleGrid.size(),obstacleGrid[].size());
}
使用数组可以通过，和上题相比，这题思路就更直接，但是效率比之前更低一点，使用的result和题目所给的格子大小一样，从右下向左上遍历，更加清晰，就是需要额外处理终点
//非递归解法
int uniquePathsWithObstacles2(vector<vector<int>>& obstacleGrid) {
/*if (obstacleGrid[0][0] == 1 || obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1])
return 0;*/
vector<vector<int>> result(obstacleGrid.size(),vector<int>(obstacleGrid[].size(),));
for (int i = obstacleGrid.size() - ; i >= ; i--) {
for (int j = obstacleGrid[].size() - ; j >= ; j--) {
if (obstacleGrid[i][j] == ) {
result[i][j] = ;
continue;
}
if (i == obstacleGrid.size() - && j == obstacleGrid[].size() - ) {
result[i][j] = ;
continue;
}
int p1 = ;
int p2 = ;
//如果是下部有位置
if (i != obstacleGrid.size() - )
p1 = result[i + ][j];
//如果是右边有位置
if (j != obstacleGrid[].size() - )
p2 = result[i][j + ];
result[i][j] = p1 + p2 ;
}
}
return result[][];
}