区间动态规划例题：最长回文子串问题（动态规划解法） 题目描述 给定一个字符串 s ，找到其中最长的回文子串（子串是连续的）。例如，若 s = "babad" ，最长回文子串可能是 "bab" 或 "aba" ；若 s = "cbbd" ，最长回文子串是 "bb" 。要求使用动态规划解决，并输出最长回文子串的长度及其具体内容。 解题思路 定义状态 设 dp[i][j] 表示字符串 s 从索引 i 到 j 的子串是否为回文（ true / false ）。 若 dp[i][j] = true ，则子串 s[i:j] 是回文。 目标：找到使 j - i + 1 最大且 dp[i][j] = true 的区间。 状态转移方程 基础情况 ： 单个字符是回文： dp[i][i] = true （长度=1）。 两个相同字符是回文： dp[i][i+1] = true （若 s[i] == s[i+1] ，长度=2）。 一般情况（长度 ≥ 3） ： 若 s[i] == s[j] 且内部子串 s[i+1:j-1] 是回文（即 dp[i+1][j-1] = true ），则 dp[i][j] = true 。 转移方程： 其中 j - i <= 2 处理长度为2或3的子串（无需检查内部）。 遍历顺序 由于 dp[i][j] 依赖 dp[i+1][j-1] （左下方），需按 子串长度从小到大 遍历： 外层循环：长度 L 从 1 到 n 。 内层循环：起始索引 i 从 0 到 n-L ，计算 j = i + L - 1 。 记录结果 在遍历时记录最大长度 maxLen 和对应的起始索引 start ，最终通过 s.substring(start, start + maxLen) 获取最长回文子串。 逐步推导（以 s = "babad" 为例） 初始化 （长度=1）： dp[0][0] = dp[1][1] = ... = dp[4][4] = true ，此时最大回文长度为1，子串为任一单字符。 长度=2 ： i=0, j=1 ： s[0]='b' != s[1]='a' → dp[0][1]=false 。 i=1, j=2 ： s[1]='a' != s[2]='b' → dp[1][2]=false 。 i=2, j=3 ： s[2]='b' != s[3]='a' → dp[2][3]=false 。 i=3, j=4 ： s[3]='a' != s[4]='d' → dp[3][4]=false 。 无新增回文子串。 长度=3 ： i=0, j=2 ： s[0]='b' == s[2]='b' 且长度=3（ j-i=2 ，满足 j-i<=2 ）→ dp[0][2]=true 。 更新 maxLen=3 , start=0 （子串 "bab" ）。 i=1, j=3 ： s[1]='a' == s[3]='a' 且内部 dp[2][2]=true → dp[1][3]=true 。 更新 maxLen=3 , start=1 （子串 "aba" ）。 i=2, j=4 ： s[2]='b' != s[4]='d' → dp[2][4]=false 。 长度=4 ： i=0, j=3 ： s[0]='b' != s[3]='a' → dp[0][3]=false 。 i=1, j=4 ： s[1]='a' != s[4]='d' → dp[1][4]=false 。 长度=5 ： i=0, j=4 ： s[0]='b' != s[4]='d' → dp[0][4]=false 。 最终最长回文子串为 "bab" 或 "aba" （长度=3）。 复杂度分析 时间复杂度：O(n²)（两层循环遍历所有子串）。 空间复杂度：O(n²)（DP表大小）。可优化至O(n)（仅存储上一行），但需保留最大子串信息。