区间动态规划例题：最长回文子串问题（Manacher算法优化版本） 题目描述 给定一个字符串s，找到s中最长的回文子串。回文串是正着读和反着读都相同的字符串。要求使用区间动态规划解决，并分析如何用Manacher算法进行优化。 解题过程 1. 问题分析 回文子串问题要求找到连续的回文子串。与回文子序列不同，子串必须是连续的。我们需要找到所有可能的子串[ i...j ]中，满足回文条件且长度最长的那个。 2. 基本动态规划解法 2.1 状态定义 定义dp[ i][ j]表示子串s[ i...j ]是否为回文串： true：s[ i...j ]是回文串 false：s[ i...j ]不是回文串 2.2 状态转移方程 对于任意子串s[ i...j ]： 如果i = j（单个字符），肯定是回文串：dp[ i][ j ] = true 如果j = i+1（两个字符），需要判断是否相等：dp[ i][ j] = (s[ i] == s[ j ]) 如果j > i+1（三个及以上字符）： dp[ i][ j] = (s[ i] == s[ j]) && dp[ i+1][ j-1 ] 2.3 算法实现步骤 初始化n×n的dp表，全部设为false 初始化最长回文子串的起始位置和长度 遍历所有可能的子串长度（从1到n） 对于每个起始位置i，计算结束位置j = i + len - 1 根据状态转移方程更新dp[ i][ j ] 如果当前子串是回文且长度大于已知最大值，更新结果 3. Manacher算法优化 3.1 为什么需要优化 基本DP解法的时间复杂度为O(n²)，空间复杂度为O(n²)。对于大规模字符串，这仍然不够高效。 3.2 Manacher算法核心思想 将原字符串插入特殊字符（如#），使所有回文子串都变成奇数长度 维护一个回文半径数组p[ i ]，表示以i为中心的最长回文半径 利用对称性避免重复计算 3.3 算法步骤 预处理：将"abc"变成"#a#b#c#" 初始化中心center=0，右边界right=0 遍历处理后的字符串： 如果i在右边界内，利用对称性：p[ i] = min(right-i, p[ 2* center-i ]) 尝试向两边扩展 如果i+p[ i ] > right，更新center和right 找到最大的p[ i ]，对应原字符串中的最长回文子串 4. 复杂度分析 基本DP：时间O(n²)，空间O(n²) Manacher算法：时间O(n)，空间O(n) 5. 实际应用建议 小规模字符串：使用基本DP解法，代码简单易懂 大规模字符串：使用Manacher算法，效率更高 竞赛场景：优先考虑Manacher算法 这种优化展示了如何通过改变问题表示方式和利用对称性，将平方级复杂度降低到线性复杂度，是区间动态规划优化的经典案例。