区间动态规划例题：最长回文子串问题 题目描述 给定一个字符串 s ，找出其中最长的连续回文子串。回文串是指正着读和反着读都相同的字符串。例如，对于字符串 "babad" ，最长回文子串可能是 "bab" 或 "aba" ；对于 "cbbd" ，最长回文子串是 "bb" 。要求时间复杂度尽量优化。 解题思路 本题可以通过 区间动态规划 来高效解决。核心思想是：如果一个子串是回文串，并且去掉首尾字符后剩下的子串仍是回文串，那么整个子串就是回文的。我们定义 dp[i][j] 表示子串 s[i:j+1] 是否为回文串（ True 或 False ），然后通过状态转移逐步扩展子串长度。 步骤详解 状态定义 设 dp[i][j] 表示字符串 s 从索引 i 到 j 的子串是否为回文串。 若 dp[i][j] = True ，说明 s[i:j+1] 是回文串。 状态转移方程 基本情况 （长度为 1 或 2 的子串）： 当 i == j ：单个字符一定是回文串，即 dp[i][j] = True 。 当 j == i+1 ：两个字符需判断是否相等，即 dp[i][j] = (s[i] == s[j]) 。 一般情况 （长度 > 2）： 若 s[i] == s[j] 且 dp[i+1][j-1] == True ，则 dp[i][j] = True 。 否则 dp[i][j] = False 。 初始化与遍历顺序 初始化：所有长度为 1 的子串先标记为回文串。 遍历顺序：由于 dp[i][j] 依赖于 dp[i+1][j-1] （即左下方的值），需按 子串长度 L 从小到大遍历： 先遍历长度 L 从 2 到 n 。 对于每个长度，遍历起始索引 i ，计算结束索引 j = i + L - 1 。 记录最长回文子串 在填充 dp 表时，若发现 dp[i][j] == True 且当前子串长度 L 大于已知最大长度，更新最长回文子串的起始位置和长度。 复杂度分析 时间复杂度：O(n²)，需要填充 n² 的 DP 表。 空间复杂度：O(n²)，用于存储 DP 表。 示例演示 以 s = "babad" 为例： 初始化所有长度为 1 的子串为回文串（如 dp[0][0] 、 dp[1][1] 等）。 长度 L=2：检查 "ba" 、 "ab" 、 "ba" 、 "ad" ，均不是回文串。 长度 L=3： i=0, j=2 ： s[0]="b" != s[2]="b" ？相等，且 dp[1][1] 为 True → "bab" 是回文串。 继续检查其他长度为 3 的子串。 最终找到最长回文子串 "bab" 或 "aba" 。 关键点总结 区间 DP 通过小区间结果推导大区间结果，避免重复计算。 遍历顺序需保证依赖的子问题已提前计算。 实际编码时可优化空间复杂度至 O(n)，但思路不变。