标签: 回文子串

最长回文子串问题寻找字符串中最长对称连续子序列，动态规划解法通过状态转移方程和空间优化求解，但内存占用高；中心扩散法空间复杂度低，适合内存受限场景。Manacher算法可实现线性时间复杂度，工程实践需权衡算法优劣，未来发展方向包括量子计算加速和硬件加速。

本文介绍了动态规划在解决最长回文子串问题中的应用。针对该问题，提供了两种解法：一种使用动态规划构建二维数组记录所有子串的回文状态，另一种采用中心扩散法，以每个字符为中心向外扩展。前者时空复杂度均为O(n^2)，后者时间复杂度为O(n^2)，空间复杂度为O(1)。