本文详解为何在实现「最大加号标志」问题时使用记忆化递归会触发 recursionerror，指出其根本原因在于无方向约束导致无限回溯，并提供高效、可扩展的四向预处理动态规划解法。
本文详解为何在实现「最大加号标志」问题时使用记忆化递归会触发 recursionerror，指出其根本原因在于无方向约束导致无限回溯，并提供高效、可扩展的四向预处理动态规划解法。
在 LeetCode 第 764 题「最大加号标志」中，目标是找出以某点为中心、四个方向（上、下、左、右）延伸出的连续非矿格（即非 mines 中坐标）所能构成的最大「加号」阶数（order）。初学者常尝试用记忆化递归（如 @cache + DFS）直接模拟“从中心向外延展”，但很快会遇到 RecursionError: maximum recursion depth exceeded —— 即使已添加边界和矿格检查，也依然失败。
根本原因在于逻辑缺陷：递归未建模「方向性」
观察原代码中的 helper(r, c)：
def helper(r,c):
if r >= n or r < 0 or c < 0 or c >= n or (r,c) in mines: return 0
return 1 + min(
helper(r + 1, c), # 下
helper(r - 1, c), # 上
helper(r, c + 1), # 右
helper(r, c - 1) # 左
)该函数试图表达：“以 (r,c) 为起点，能向四个方向各延伸多远？取最小值即为该点的加号阶数”。但问题在于：helper(r+1,c) 会调用 helper(r,c)（因为向上走一步就回到原点），而 helper(r,c) 又再次调用 helper(r+1,c)……形成 无终止的双向依赖环。即使有 @cache，缓存的是 (r,c) 的返回值，但该值本身依赖于尚未计算完成的邻居——而由于无方向约束，递归图存在环，导致栈深度线性增长直至溢出。
✅ 正确思路：将“中心向外延伸”转化为“单向累积统计”
我们不再对每个点做四向 DFS，而是预处理四个方向的连续安全格长度：
- top[i][j]：从第 i 行第 j 列向上（含自身）最多有多少个连续非矿格；
- bot[i][j]：向下；
- left[i][j]：向左；
- right[i][j]：向右。
每个方向均可通过一次扫描 O(n²) 完成，且天然无环、无回溯。
以下是优化后的完整实现（已适配 Python 3.9+，使用 range(n) 和解包语法）：
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
# 将 mines 转为集合，支持 O(1) 查找
mine_set = {tuple(mine) for mine in mines}
R = range(n)
# 初始化四向 DP 数组
top = [[0] * n for _ in R]
bot = [[0] * n for _ in R]
left = [[0] * n for _ in R]
right = [[0] * n for _ in R]
# ? 从左到右、从上到下：计算 top 和 left
for i in R:
s_top = s_left = 0
for j in R:
# top[i][j]：第 i 行、第 j 列向上连续安全格数（含本格）
if (i, j) in mine_set:
s_top = 0
else:
s_top += 1
top[i][j] = s_top
# left[j][i]：注意此处巧妙转置——用于后续计算第 i 列从上到下的 left 累积？
# 实际更清晰的做法是分开两层循环；下方采用标准四向扫描法重写以增强可读性
# ✅ 推荐更清晰的四次独立扫描（见下方修正版）为提升可读性与正确性，我们采用四次明确方向的线性扫描：
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
mine_set = {tuple(mine) for mine in mines}
R = range(n)
# 四个方向 DP 表：dp_dir[i][j] 表示从 (i,j) 出发沿 dir 方向的连续安全格数量（含自身）
up = [[0] * n for _ in R]
down = [[0] * n for _ in R]
left = [[0] * n for _ in R]
right = [[0] * n for _ in R]
# ? 向上扫描：每列从上到下累积
for j in R:
cnt = 0
for i in R:
if (i, j) in mine_set:
cnt = 0
else:
cnt += 1
up[i][j] = cnt
# ? 向下扫描：每列从下到上累积
for j in R:
cnt = 0
for i in reversed(R):
if (i, j) in mine_set:
cnt = 0
else:
cnt += 1
down[i][j] = cnt
# ◀️ 向左扫描：每行从左到右累积
for i in R:
cnt = 0
for j in R:
if (i, j) in mine_set:
cnt = 0
else:
cnt += 1
left[i][j] = cnt
# ▶️ 向右扫描：每行从右到左累积
for i in R:
cnt = 0
for j in reversed(R):
if (i, j) in mine_set:
cnt = 0
else:
cnt += 1
right[i][j] = cnt
# ? 对每个位置 (i,j)，其最大加号阶数 = 四方向最小值
ans = 0
for i in R:
for j in R:
cross = min(up[i][j], down[i][j], left[i][j], right[i][j])
ans = max(ans, cross)
return ans关键优势总结：
- ✅ 时间复杂度：O(n²)，远优于错误递归的指数/无限复杂度；
- ✅ 空间复杂度：O(n²)，可接受（n ≤ 500）；
- ✅ 无递归调用，彻底规避栈溢出风险；
- ✅ 逻辑清晰、可验证：每步扫描对应一个物理方向，易于调试与单元测试。
注意事项：
- mines 必须转为 set（而非 list），否则 in 操作退化为 O(k)，整体变慢；
- 四个 DP 数组不可复用同一内存（如误用 [[0]*n]*n），需确保每行独立；
- 边界处理已隐含在扫描逻辑中（cnt=0 重置），无需额外判断；
- 若需空间优化，可只保留两个方向数组并滚动更新，但可读性下降，通常不必要。
掌握这种「将循环依赖递归重构为单向动态规划」的思维，是解决网格类 DFS 陷阱题的关键跃迁。
