区间动态规划例题：最长回文子串问题 题目描述 给定一个字符串 s，找到 s 中最长的回文子串。回文串是正着读和反着读都一样的字符串。例如，对于输入 "babad"，最长回文子串可能是 "bab" 或 "aba"；对于输入 "cbbd"，最长回文子串是 "bb"。要求使用区间动态规划解决。 解题思路 定义状态：dp[ i][ j ] 表示字符串 s 从索引 i 到 j 的子串是否为回文串（True 或 False）。 状态转移方程： 如果子串长度为 1（即 i == j），则 dp[ i][ j ] = True。 如果子串长度为 2（即 j == i+1），则 dp[ i][ j] = (s[ i] == s[ j ])。 如果子串长度大于 2，则 dp[ i][ j] = (s[ i] == s[ j]) and dp[ i+1][ j-1 ]。 初始化：所有长度为 1 的子串都是回文串。 填表顺序：由于 dp[ i][ j] 依赖于 dp[ i+1][ j-1 ]（即左下方的状态），需要按子串长度从小到大遍历。 记录结果：在遍历过程中记录最长的回文子串起始位置和长度。 详细步骤 初始化一个二维数组 dp，大小为 n×n（n 为字符串长度），初始值为 False。 所有长度为 1 的子串都是回文串：遍历 i 从 0 到 n-1，设置 dp[ i][ i ] = True。此时最长回文子串长度为 1，记录起始位置为当前 i。 处理长度为 2 的子串：遍历 i 从 0 到 n-2，检查 s[ i] 和 s[ i+1] 是否相等。若相等，设置 dp[ i][ i+1 ] = True，并更新最长回文子串的起始位置和长度（长度为 2）。 处理长度大于等于 3 的子串：设长度 L 从 3 到 n，遍历起始索引 i 从 0 到 n-L，计算结束索引 j = i+L-1。检查 s[ i] 和 s[ j] 是否相等，且内部子串 dp[ i+1][ j-1] 是否为 True。若满足，设置 dp[ i][ j ] = True，并更新最长回文子串的起始位置和长度。 最终根据记录的起始位置和长度，返回对应的子串。 举例说明 以 s = "babad" 为例： 初始化：所有 dp[ i][ i ] = True，最长子串为 "b"（长度 1）。 长度 2：检查 "ba"、"ab"、"ba"、"ad"，均不相等，无更新。 长度 3：检查子串 "bab"：s[ 0] == s[ 2]（'b'=='b'）且 dp[ 1][ 1]（内部 "a"）为 True，故 dp[ 0][ 2 ] = True，记录长度为 3。类似地，"aba" 也满足，但起始位置不同。 最终最长回文子串为 "bab" 或 "aba"。 通过以上步骤，即可高效找到最长回文子串。