Unique Paths II问题：自实现递归方案的段错误排查求助

思路正确性判断 #

你的思路方向没问题——通过判断上方/左方单元格是否为障碍物来决定是否能从该方向抵达当前位置，但存在逻辑漏洞：

• 视频里先检查当前单元格是否为-1，是提前终止无效路径：如果当前格子本身是障碍物，直接返回0，避免无意义的递归。
• 你的方案只检查来向单元格，却忽略了当前单元格本身就是障碍物的情况，这会导致递归继续进入无效区域，甚至触发越界。

段错误的核心原因 #

段错误几乎都是数组越界访问导致的，常见场景：

• 递归时未正确处理边界（比如行/列索引小于0时仍尝试访问数组）
• 检查上方/左方单元格前，没有先判断该单元格是否在合法范围内，直接访问导致越界

修复后的递归逻辑示例 #

假设你的递归函数为countPaths(i, j, grid)，核心逻辑应调整为：

# 先处理边界与当前单元格有效性：越界或当前是障碍物，直接返回0
if i < 0 or j < 0 or grid[i][j] == -1:
    return 0
# 到达起点（假设起点是(0,0)），返回1条有效路径
if i == 0 and j == 0:
    return 1
# 递归计算上方和左方的路径数（已通过前置判断确保不会越界或访问障碍物）
up = countPaths(i-1, j, grid)
left = countPaths(i, j-1, grid)
return up + left

额外提示 #

递归确实会超时，后续可以通过记忆化搜索（缓存(i,j)的计算结果）优化，这也是该问题动态规划解法的核心思路。

内容的提问来源于stack exchange，提问作者Tanish Sharma