bobo老师麻烦帮我看看力扣63题(不同路径II障碍物)
来源：9-3 发现重叠子问题 Integer Break
慕粉张张张
2021-08-17
- 我还是想用递归+记忆数组的思路来写，有个特别长的测试用例过不去，bobo老师麻烦你帮我看一下思路有没有问题
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>>memo(m + 1 , vector<int>(n + 1 , - 1));
int ret = uniquePathsWithObstacles(obstacleGrid,memo,m - 1 , n - 1);
return ret;
}
private:
//需要向上走x步，向左走y步的路径总数
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid,vector<vector<int>>& memo,int x, int y)
{
//递归到底的情况
//x == 0向上走到头了往左看看y方向有没有障碍物
if(x == 0)
{
for(int i = 0 ; i < obstacleGrid[0].size() ; i ++)
{
if(obstacleGrid[0][i] == 1)
return 0;
}
return 1;
}
//y == 0向左走到头了，找x(上)看看x方向有没有障碍
if(y == 0)
{
for(int i = 0 ; i < obstacleGrid.size() ; i ++)
{
if(obstacleGrid[i][0] == 1)
return 0;
}
return 1;
}
if(memo[x][y] != -1)
return memo[x][y];
//当前位置就是障碍
if(obstacleGrid[x][y] == 1)
{
memo[x][y] = 0;
return 0;
}
int pathNums1 = uniquePathsWithObstacles(obstacleGrid,memo,x - 1,y);
int pathNums2 = uniquePathsWithObstacles(obstacleGrid,memo,x,y - 1);
memo[x][y] = pathNums1 + pathNums2 ;
return memo[x][y];
}
};
2回答
-
递归走到头的时候，不应该看整个第 0 行或者第 0 列，而应该看第 0 行 y 以前或者第 0 列 x 以前：
if(x == 0){ // 注意，是 i <= y for(int i = 0 ; i <= y ; i ++) { if(obstacleGrid[0][i] == 1) return 0; } return 1; } if(y == 0){ // 注意，是 i <= x for(int i = 0 ; i <= x ; i ++) { if(obstacleGrid[i][0] == 1) return 0; } return 1; }继续加油！：）
112021-08-17 -
慕粉张张张
提问者
2021-08-17
经典自问自答，递归中止条件写错了！！！应该这样写！
//递归到底的情况
//x == 0找y(左)看看y方向有没有障碍
if(x == 0)
{
//i的初值应该从y开始，往前找有没有障碍物
for(int i = y ; i >= 0 ; i --)
{
if(obstacleGrid[0][i] == 1)
return 0;
}
return 1;
}
//y == 0找x(上)看看x方向有没有障碍
if(y == 0)
{
//i的初值应该从x开始，往前找有没有障碍物
for(int i = x ; i >= 0 ; i --)
{
if(obstacleGrid[i][0] == 1)
{
return 0;
}
}
return 1;
}
00
相似问题