本文深入剖析暴力递归解法导致内存超限（mle）的根本原因，详解基于动态规划的 o(n²) 空间优化实现，并提供可直接提交的高效、稳定代码。
本文深入剖析暴力递归解法导致内存超限（mle）的根本原因，详解基于动态规划的 o(n²) 空间优化实现，并提供可直接提交的高效、稳定代码。
在 LeetCode 第 5 题「最长回文子串」中，看似简洁的递归 + 记忆化思路（如维护 checked_words 集合）实则暗藏严重性能陷阱。你提供的代码虽在本地测试仅占用约 128MB 内存，但在 LeetCode 在线判题环境中触发 Memory Limit Exceeded（MLE），其核心原因并非单纯“内存用量大”，而是指数级的递归调用栈深度与冗余子问题爆炸式生成——这导致实际内存开销远超 sys.getsizeof() 所能反映的静态集合大小。
❌ 为什么你的递归解法会 MLE？
你的 dp(word) 函数对每个子串 word 递归调用两次：dp(word[:-1]) 和 dp(word[1:])。对于长度为 n 的字符串，该过程会生成 O(2ⁿ) 个不同子串节点（即使去重，递归调用栈深度也达 O(n)，且每层需保存多个字符串副本）。更关键的是：
- word[:-1] 和 word[1:] 均创建新字符串对象（Python 中字符串不可变），引发大量内存分配；
- checked_words 存储的是字符串对象本身，而长输入中存在海量重复子串（如连续 'v' 或 'z'），但哈希集无法避免中间字符串的瞬时构造开销；
- is_palindrom() 每次都做 O(k) 全量扫描（k 为子串长度），整体时间复杂度高达 O(n³)，进一步加剧运行时资源争抢。
✅ 正确方向：避免生成所有子串，转而枚举子串边界并复用已有结果。
✅ 动态规划解法：空间可控、逻辑清晰、稳定通过
我们采用二维 DP 表 dp[i][j] 表示子串 s[i..j]（闭区间）是否为回文。状态转移遵循回文本质：
- 单字符必为回文：dp[i][i] = True
- 双字符需相等：dp[i][i+1] = (s[i] == s[i+1])
- 长度 ≥3 时：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
该方法时间复杂度为 O(n²)，空间复杂度也为 O(n²)，但内存布局紧凑（纯布尔二维数组），无字符串拷贝，且可通过滚动更新进一步压缩至 O(n)，但本题 n ≤ 1000，O(n²) 完全可接受。
以下是经过 LeetCode 实测、100% 通过的优化实现：
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return ""
# dp[i][j] 表示 s[i:j+1] 是否为回文
dp = [[False] * n for _ in range(n)]
start, max_len = 0, 1 # 记录最长回文起始位置与长度
# 所有长度为 1 的子串都是回文
for i in range(n):
dp[i][i] = True
# 检查长度为 2 的子串
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start, max_len = i, 2
# 枚举长度 L 从 3 到 n
for L in range(3, n + 1):
for i in range(n - L + 1):
j = i + L - 1 # 子串右端点
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
start, max_len = i, L
return s[start:start + max_len]? 关键优化点说明
- 无字符串切片递归：完全规避 word[:-1]/word[1:] 引发的内存复制；
- 原地状态更新：dp 表仅存储布尔值，每个元素占 1 字节（实际 Python 中略高，但仍远小于字符串对象）；
- 边界驱动枚举：按子串长度升序填充 DP 表，确保 dp[i+1][j-1] 总是已计算；
- 只存最优解坐标：不缓存所有候选子串，仅记录 start 和 max_len，最终一次切片返回结果。
⚠️ 注意事项与进阶提示
- 不要盲目使用 lru_cache：对 is_palindrom(sub) 缓存看似合理，但子串数量仍为 O(n²)，且缓存键为字符串对象，内存开销不亚于原始方案；
- 中心扩展法（O(n²) 时间 + O(1) 空间）更省内存：以每个位置为中心向两侧扩展，无需 DP 表，适合内存极度受限场景；
- Manacher 算法（O(n)）是理论最优：但实现复杂、常数较大，LeetCode 中非必需；DP 解法在可读性、稳定性与性能间取得最佳平衡。
掌握此 DP 范式，不仅解决本题，更为「子串类动态规划」（如最长重复子串、分割回文串等）奠定坚实基础。真正的算法优化，始于对问题结构的洞察，而非对局部变量的微观调优。
