区间动态规划例题：最长回文子串的个数问题 题目描述 给定一个字符串 s ，请统计其中回文子串的个数。回文子串要求是连续的，且正读反读相同。例如，字符串 "aaa" 的回文子串包括 "a" 、 "a" 、 "a" 、 "aa" 、 "aa" 、 "aaa" ，总数为 6。 解题思路 问题分析 ： 回文子串的长度可能为奇数或偶数，传统中心扩展法需分情况处理。区间动态规划通过 dp[i][j] 记录子串 s[i:j] 是否为回文，从而避免重复计算。 状态定义 ： 设 dp[i][j] 表示子串 s[i...j] 是否为回文串（ true / false ）。 状态转移方程 ： 若子串长度为 1（即 i == j ），则必为回文。 若子串长度为 2（即 j == i+1 ），则需满足 s[i] == s[j] 。 若长度大于 2，则需满足 s[i] == s[j] 且内部子串 s[i+1][j-1] 是回文（即 dp[i+1][j-1] == true ）。 综上： \[ 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{true} \\ \text{false} & \text{otherwise} \end{cases} \] 初始化与遍历顺序 ： 初始化：所有长度为 1 的子串设为回文。 遍历时需按子串长度从小到大处理，先计算短区间再推长区间。外层循环枚举长度 L ，内层循环枚举起始点 i 。 统计结果 ： 遍历所有 dp[i][j] ，统计值为 true 的个数。 详细步骤 初始化长度为 n 的二维数组 dp ，全部设为 false 。 处理长度为 1 的子串：对每个 i ，设置 dp[i][i] = true ，并计数加 1。 处理长度为 2 的子串：对每个 i ，若 s[i] == s[i+1] ，设置 dp[i][i+1] = true ，计数加 1。 处理长度 L ≥ 3 的子串： 遍历起始索引 i ，计算终点 j = i + L - 1 。 若 s[i] == s[j] 且 dp[i+1][j-1] 为真，则设置 dp[i][j] = true ，计数加 1。 返回总计数。 示例分析（s = "aaa"） 长度 1： (0,0) , (1,1) , (2,2) → 计数 3。 长度 2： (0,1) ： s[0]=s[1] → 计数 +1 (1,2) ： s[1]=s[2] → 计数 +1 长度 3： (0,2) ： s[0]=s[2] 且 dp[1][1]=true → 计数 +1 总计数 = 3 + 2 + 1 = 6。 核心逻辑 通过区间 DP 将回文判断的复杂度从暴力法的 O(n³) 优化至 O(n²)，同时准确统计所有连续回文子串。