区间动态规划例题：最长回文子串问题（中心扩展与DP结合版本） 题目描述 给定一个字符串 s ，找到其中最长的回文子串。回文串是正着读和反着读都相同的字符串。例如，对于输入 "babad" ，最长回文子串可能是 "bab" 或 "aba" ；对于输入 "cbbd" ，最长回文子串是 "bb" 。要求时间复杂度尽量优化。 解题思路 本题可以通过区间动态规划（DP）来高效解决。我们定义 dp[i][j] 表示子串 s[i..j] 是否为回文串。通过填充一个二维 DP 表，我们可以利用已知的小区间回文信息判断更大区间是否为回文，同时记录最长回文的起始位置和长度。 步骤详解 状态定义 设 dp[i][j] 是一个布尔值，表示字符串 s 从索引 i 到 j 的子串是否为回文串。 初始化：所有长度为 1 的子串都是回文串（即 dp[i][i] = true ）。 状态转移方程 如果子串长度大于 1，判断 s[i] 和 s[j] 是否相等： 若 s[i] != s[j] ，则 dp[i][j] = false 。 若 s[i] == s[j] ，还需根据子串长度进一步判断： 如果子串长度为 2（即 j == i+1 ），则 dp[i][j] = true 。 如果子串长度大于 2，则 dp[i][j] = dp[i+1][j-1] （即内部子串必须是回文）。 转移方程总结： \[ dp[ i][ j ] = \begin{cases} \text{true} & \text{if } i = j \\ \text{true} & \text{if } j = i+1 \text{ and } s[ i] = s[ j ] \\ \text{true} & \text{if } j > i+1 \text{ and } s[ i] = s[ j] \text{ and } dp[ i+1][ j-1 ] \\ \text{false} & \text{otherwise} \end{cases} \] 填充顺序与记录结果 由于 dp[i][j] 依赖于 dp[i+1][j-1] （即左下方的值），我们按子串长度 L 从 2 到 n 的顺序遍历。 同时维护变量 start 和 maxLen ，当发现 dp[i][j] == true 且当前长度 L = j-i+1 > maxLen 时，更新 maxLen = L 和 start = i 。 示例演示（s = "babad"） 初始化：所有单个字符都是回文（如 dp[0][0] = true ）。 长度 L=2：检查 "ba", "ab", "ba", "ad" → 无回文。 长度 L=3： "bab"： s[0] == s[2] 且内部 "a" 是回文 → dp[0][2] = true ，更新 maxLen=3 , start=0 。 "aba"：同理 dp[1][3] = true ，但长度相同，可保留任意一个。 长度 L=4：无新增回文。 长度 L=5：整个字符串不是回文。 最终结果：从 start=0 开始长度为 3 的子串 "bab" 。 复杂度分析 时间复杂度：O(n²)，需要填充 n² 大小的 DP 表。 空间复杂度：O(n²)，可优化为 O(n)（但本题需输出子串，通常保留二维表）。 关键点 通过小区间回文信息推导大区间，避免重复计算。 按长度递增的顺序填充 DP 表，确保依赖项先被计算。 对比纯中心扩展法（O(n²) 时间、O(1) 空间），DP 方法更直观易理解，适合区间动态规划的学习。