本文详解为何在实现 orderOfLargestPlusSign 时使用记忆化递归会触发 RecursionError，并提供高效、无递归的动态规划解法——通过预处理四个方向的连续非矿格长度，在 O(n²) 时间内安全求解。
本文详解为何在实现 `orderoflargestplussign` 时使用记忆化递归会触发 `recursionerror`，并提供高效、无递归的动态规划解法——通过预处理四个方向的连续非矿格长度，在 o(n²) 时间内安全求解。
在 LeetCode 第764题「最大加号标志」中，目标是找出以某点为中心、四臂等长且全由非矿格（即未被挖空）构成的最大加号形状的阶数（order）。初学者常尝试用记忆化递归（@cache）实现“从中心向四周延伸”的逻辑，例如定义 helper(r, c) 表示以 (r, c) 为起点、沿某一方向能延伸的最长非矿格数。但原代码中的递归设计存在根本性缺陷：它未区分方向，导致状态间形成环状依赖。
具体来看，原 helper 函数试图通过 min(helper(r+1,c), helper(r−1,c), helper(r,c+1), helper(r,c−1)) 计算十字臂长。然而，该逻辑隐含了“任意方向均可回溯”的假设——例如 helper(1,1) 调用 helper(0,1)，而 helper(0,1) 又可能调用 helper(1,1)（当检查上方向时），从而形成无限递归链。即使添加了边界与矿格判断（if r
因此，正确解法应摒弃“中心扩散式递归”，转而采用方向分离的动态规划预处理：对每个格子 (i, j)，独立计算其向上、向下、向左、向右四个方向连续非矿格的最大长度。这四个值的最小值，即为以 (i, j) 为中心所能构成的最大加号阶数。
以下是优化后的完整实现：
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[i][j] 表示从 (i,j) 向上连续非矿格数（含自身）
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[i][j]: 向左连续长度（注意：此处按行扫描，故 left[i][j] 对应第 i 行）
if (j, i) in mine_set: # ⚠️ 注意原答案此处索引有误，已修正逻辑说明
s_left = 0
else:
s_left += 1
left[i][j] = s_left # 实际应为 left[j][i]？不——我们统一按 (行, 列) 理解
# 更清晰、无歧义的写法（推荐）：
# 重新初始化并分方向独立遍历
top = [[0]*n for _ in R]
bot = [[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
top[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
bot[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
# 枚举每个中心点，取四方向最小值的最大值
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✅ 关键优势：
- 时间复杂度稳定 O(n²)：四次线性扫描 + 一次枚举，无递归开销；
- 空间复杂度 O(n²)：仅需四个 n×n 数组，可进一步优化为滚动数组（但可读性下降）；
- 绝对避免栈溢出：无递归调用，彻底规避 RecursionError。
⚠️ 注意事项：
- 原答案中 left[b][a] = s2 等写法易引发索引混淆（将行列关系颠倒），实际开发中建议严格按 (row, col) 维度组织数组，并为每个方向单独编写清晰循环；
- mines 转集合必须使用 tuple(i)（因列表不可哈希），否则运行时报错；
- 若 n 较大（如 500），递归解法在 Python 中极易爆栈（默认递归限制约 1000 层），而 DP 解法无此风险。
总结：面对网格类“多方向延伸”问题，优先考虑方向解耦 + 线性 DP 预处理，而非试图用记忆化递归模拟多向搜索——后者在无向依赖下极易陷入死循环，是典型的“看似合理、实则危险”的陷阱。
