区间动态规划例题：最长回文子串问题（不同解法版本） 题目描述 给定一个字符串 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] && dp[i+1][j-1]) （首尾字符相同且内部子串是回文）。 边界条件 ：当 i > j 时无需处理（默认 false ）。 记录结果 ：在填充 dp 表时，同步记录最长回文子串的起始位置和长度。 逐步求解 以 s = "babad" 为例： 初始化 ：创建一个 5×5 的 dp 表（索引 0 到 4），初始全部为 false 。 填充基础情况 ： 所有长度为 1 的子串（ i == j ）均为回文： dp[0][0] = true , dp[1][1] = true , ..., dp[4][4] = true 。 长度为 2 的子串： dp[0][1] = (s[0]=='b' == s[1]=='a')? false ， dp[1][2] = (s[1]=='a' == s[2]=='b')? false ， dp[2][3] = (s[2]=='b' == s[3]=='a')? false ， dp[3][4] = (s[3]=='a' == s[4]=='d')? false 。 填充长度 ≥ 3 的子串 （按子串长度由小到大遍历）： 长度 3： dp[0][2] = (s[0]=='b' == s[2]=='b')? true && dp[1][1]=true → true （子串 "bab" 是回文）。 dp[1][3] = (s[1]=='a' == s[3]=='a')? true && dp[2][2]=true → true （子串 "aba" 是回文）。 dp[2][4] = (s[2]=='b' == s[4]=='d')? false → false 。 长度 4： dp[0][3] = (s[0]=='b' == s[3]=='a')? false → false 。 dp[1][4] = (s[1]=='a' == s[4]=='d')? false → false 。 长度 5： dp[0][4] = (s[0]=='b' == s[4]=='d')? false → false 。 记录最长回文子串 ：在填充过程中，当 dp[i][j] = true 时，比较当前子串长度 j-i+1 与已知最大值。本例中长度为 3 的回文子串有两个（"bab" 和 "aba"），任选一个即可。 复杂度分析 时间复杂度：O(n²)，需要填充 n² 大小的 dp 表。 空间复杂度：O(n²)，用于存储 dp 表。