本文详解为何在实现“最大十字形标志”问题时使用记忆化递归会触发 recursionerror，并提供基于动态规划的高效替代方案，通过预计算四个方向的连续非雷长度来避免递归陷阱。
本文详解为何在实现“最大十字形标志”问题时使用记忆化递归会触发 recursionerror，并提供基于动态规划的高效替代方案，通过预计算四个方向的连续非雷长度来避免递归陷阱。
在 LeetCode 第 764 题「最大十字形标志」中，目标是找出以某点为中心、四臂等长且全由非雷格子构成的最大“+”形边长（即阶数）。初学者常尝试用记忆化递归（@cache）直接定义 helper(r, c) 表示以 (r, c) 为中心能延伸出的最大臂长——但该思路存在根本性逻辑缺陷：递归未体现方向性约束，导致无限循环调用。
例如，helper(1,1) 可能调用 helper(0,1)，而后者又调用 helper(1,1)（因无方向限制，向上后可立即向下返回），形成环状依赖。即使添加了越界和雷点的 base case，@cache 也无法打破这种双向可达性，最终耗尽 Python 默认约 1000 层的递归栈，抛出 RecursionError: maximum recursion depth exceeded。
✅ 正确解法应放弃“中心向外递归”，转而采用四向动态规划预处理：对每个格子 (i, j)，分别计算其向上、向下、向左、向右四个方向连续非雷格子的数量（含自身）。这四个值的最小值，即为以该点为中心的最大十字阶数。
以下是优化后的完整实现：
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
# 将 mines 转为 set 便于 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:
up_cnt = left_cnt = 0
for j in R:
# top[i][j]: 向上连续非雷数（同一列，行递增）
if (i, j) in mine_set:
up_cnt = 0
else:
up_cnt += 1
top[i][j] = up_cnt
# left[i][j]: 向左连续非雷数（同一行，列递增）
if (j, i) in mine_set: # 注意：此处利用对称索引填 left[b][a]
left_cnt = 0
else:
left_cnt += 1
left[j][i] = left_cnt
# 第二遍：从下到上、从右到左 → 填充 bot 和 right
for i in R:
down_cnt = right_cnt = 0
for j in reversed(R):
if (i, j) in mine_set:
down_cnt = 0
else:
down_cnt += 1
bot[i][j] = down_cnt
if (j, i) in mine_set:
right_cnt = 0
else:
right_cnt += 1
right[j][i] = right_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⚠️ 关键注意事项：
- 索引对称技巧：代码中 left[j][i] 和 right[j][i] 的写法是为了复用同一层循环同时更新列方向（top/bot）与行方向（left/right）的 DP 值，本质是利用矩阵转置思想提升缓存局部性，非必需但更简洁；你也可拆分为两个独立双循环，逻辑更直观。
- 时间复杂度：O(n²)，远优于错误递归的指数级或不可控深度；
- 空间复杂度：O(n²)，用于存储四张 DP 表；
- 边界安全：所有 DP 表初始化为 0，雷点处显式置 0，天然满足边界条件，无需额外判断。
总结：当递归状态转移不满足无后效性或方向单调性（如本例中“中心→四邻”无法保证路径终止）时，强行记忆化只会掩盖设计缺陷。此时应回归问题本质——十字形由四个一维连续段构成，分方向线性扫描是最自然、最稳健的建模方式。
