求带障碍网格寻路DFS算法的时间复杂度
2026-9-27
关于算法实现的相关问题解答
一、是否属于记忆化搜索
不属于标准记忆化搜索。
常规记忆化搜索的核心逻辑是：每个状态的结果一旦计算完成就永久固定，后续遇到相同状态直接读取缓存返回，不会重复计算，比如你提到的记忆化斐波那契就是典型案例。
你当前的实现只能算作路径剪枝优化：只有当新路径的步数小于当前格子已存储的步数时，才会更新并继续递归，只是过滤了明显更差的路径，同一个格子可能会被多次更新、多次触发后续递归，不符合记忆化的特征。
二、时间复杂度分析
- 最坏理论上限确实是你猜测的
O(4^(row*col))：如果剪枝逻辑完全失效，比如每次到达同一格子的步数都比之前的存储值更小，每次都要触发四个方向的递归，就会达到这个指数级复杂度。 - 实际运行效率远高于最坏上限：因为剪枝规则的存在，只要新路径的步数大于等于当前格子的已知最小步数就会直接返回，不会继续递归。对于无特殊构造的普通网格，每个格子通常只会被更新1到3次，实际运行效率接近
O(row*col)。 - 注意该算法的最坏复杂度仍然是指数级，并不适合作为网格最短路径的标准解法，面试场景下这类网格最短路径题的最优方案是BFS，时间复杂度稳定为
O(row*col)，天然按步数从小到大遍历，第一次到达终点的步数就是最小值，不需要重复更新单元格。
三、代码中的明显错误
你提供的代码存在几处语法和逻辑错误，会导致运行失败：
- 所有出现
grid[row][cell]的位置，cell应为col，属于变量名书写错误 newStep == currStep+1、grid[row][cell] == currStep+1两处是赋值逻辑，应该用单等号=而非双等号==- 边界判断逻辑错误：
row > lenRow || col > lenCol应改为row >= lenRow || col >= lenCol，数组下标从0开始，合法最大值为长度减1
内容的提问来源于stack exchange，提问作者Rajan
相关产品推荐
相关产品推荐
