本文详解为何在 orderOfLargestPlusSign 问题中使用记忆化递归会触发 RecursionError，并提供高效、非递归的动态规划解法——通过预处理四个方向的连续非矿格长度，在 O(n²) 时间内安全求解。
本文详解为何在 `orderoflargestplussign` 问题中使用记忆化递归会触发 `recursionerror`，并提供高效、非递归的动态规划解法——通过预处理四个方向的连续非矿格长度，在 o(n²) 时间内安全求解。
在 LeetCode 第 764 题「最大加号标志」中，目标是找出一个以某格为中心、四臂等长（上下左右延伸均为 1）的最大加号形状，其阶数（order）即为臂长。初学者常尝试用记忆化递归（如 @cache + DFS）直接定义 helper(r, c) 表示以 (r, c) 为中心能形成的最大加号阶数。但该思路存在根本性逻辑缺陷：
❌ 问题根源：递归定义不满足有向无环性
原代码中：
ans = 1 + min(
helper(r + 1, c), # 下
helper(r - 1, c), # 上
helper(r, c + 1), # 右
helper(r, c - 1) # 左
)helper(r, c) 依赖于其邻接格子的 helper 值，而这些邻接格子又会反过来依赖 (r, c)（例如 helper(r+1, c) 调用 helper(r, c) 作为“上”方向），形成隐式循环依赖。即使添加了 @cache 和边界/矿格判断，缓存也无法打破这种双向调用链——因为 helper 的语义是“以该点为中心的阶数”，而非“从该点向某方向可延伸的长度”。这导致栈深度随 n 指数级增长，最终触发 RecursionError: maximum recursion depth exceeded。
✅ 正确解法：方向分离 + 动态规划预处理
核心思想是将问题解耦：不直接求“中心阶数”，而是分别预计算每个格子向上、下、左、右四个方向连续非矿格的最大长度，再对每个格子取四者最小值，即为其作为中心时的最大加号阶数。
- top[i][j]：从 (i,j) 向上（行减小）连续非矿格数量（含自身）
- bot[i][j]：向下连续长度
- left[i][j]：向左连续长度
- right[i][j]：向右连续长度
这些数组均可通过两次扫描（正向 + 反向） 在 O(n²) 内完成，完全避免递归：
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
mine_set = {tuple(m) for m in mines} # O(1) 查找
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]: 从第0行到第i行，(i,j)向上连续非矿数
if (i, j) in mine_set:
s_top = 0
else:
s_top += 1
top[i][j] = s_top
# left[i][j]: 从第0列到第j列，(i,j)向左连续非矿数
if (j, i) in mine_set: # 注意：此处利用对称性，(j,i)对应left[j][i]
s_left = 0
else:
s_left += 1
left[j][i] = s_left # 即 left[col][row] = 向左长度
# 反向扫描：计算 bot 和 right
for i in R:
s_bot = s_right = 0
for j in reversed(R):
if (i, j) in mine_set:
s_bot = 0
else:
s_bot += 1
bot[i][j] = s_bot
if (j, i) in mine_set:
s_right = 0
else:
s_right += 1
right[j][i] = s_right
# 枚举每个中心点，取四方向最小值的最大值
ans = 0
for i in R:
for j in R:
arm = min(top[i][j], bot[i][j], left[i][j], right[i][j])
ans = max(ans, arm)
return ans? 关键实现细节说明：
- 使用 set 存储 mines，确保 O(1) 矿格查询；
- 利用坐标对称性（如 left[j][i] 对应位置 (i,j) 的左向长度），减少循环嵌套层级，提升可读性；
- 每次扫描中，遇到矿格则重置计数器 s_* = 0，否则累加，自然体现“连续”含义；
- 最终 min(top[i][j], bot[i][j], left[i][j], right[i][j]) 即是以 (i,j) 为中心的最大加号臂长——因为加号四臂必须同时存在且等长。
? 总结与建议：
当问题涉及“多方向依赖”且递归状态易形成环时（尤其网格类 DFS），优先考虑方向解耦 + DP 预处理。本题时间复杂度 O(n²)，空间复杂度 O(n²)，稳定高效，无栈溢出风险。切勿强行套用记忆化递归而不验证状态转移的拓扑序——这是导致 RecursionError 的最常见深层原因。
