区间动态规划例题：最长回文子串问题

题目描述
给定一个字符串 s，找到其中最长的回文子串（子串是连续的）。例如，若 s = "babad"，最长回文子串可能是 "bab" 或 "aba"；若 s = "cbbd"，最长回文子串是 "bb"。要求时间复杂度优化至 \(O(n^2)\)，空间复杂度优化至 \(O(n^2)\) 或更低。

解题思路

1. 定义状态
   设 dp[i][j] 表示字符串从索引 i 到 j 的子串是否为回文（true/false）。

2. 状态转移方程

   • 如果子串长度为 1（即 i == j），则一定是回文。
   • 如果子串长度为 2（即 j == i+1），则需判断 s[i] == s[j]。
   • 如果长度大于 2，则需满足：

     dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
     

     即首尾字符相等，且中间子串也是回文。

3. 边界与初始化

   • 初始时，所有长度为 1 的子串均为回文。
   • 记录最长回文的起始位置和长度，在遍历过程中更新。

4. 遍历顺序
   由于 dp[i][j] 依赖 dp[i+1][j-1]（即左下方的值），需按子串长度从小到大遍历：

   • 先遍历长度 L = 2 到 n，再遍历起始索引 i。

逐步推导示例
以 s = "babad" 为例：

1. 初始化长度为 1 的回文：

   dp[0][0]=true, dp[1][1]=true, ..., dp[4][4]=true
   

   此时最长回文长度为 1，起始位置为任意单字符。

2. 长度 L=2：

   • i=0, j=1："ba" → s[0]!=s[1] → false
   • i=1, j=2："ab" → false
   • i=2, j=3："ba" → false
   • i=3, j=4："ad" → false
     无新增回文。

3. 长度 L=3：

   • i=0, j=2："bab" → s[0]==s[2] 且 dp[1][1]=true → true
     更新最长回文为 "bab"（长度 3）。
   • i=1, j=3："aba" → s[1]==s[3] 且 dp[2][2]=true → true
     更新为 "aba"（长度 3）。
   • i=2, j=4："bad" → s[2]!=s[4] → false

4. 长度 L=4：

   • i=0, j=3："baba" → s[0]!=s[3] → false
   • i=1, j=4："abad" → s[1]!=s[4] → false

5. 长度 L=5：

   • i=0, j=4："babad" → s[0]!=s[4] → false

最终最长回文子串为 "bab" 或 "aba"。

算法优化

• 空间复杂度可优化至 \(O(n)\)：遍历时只需保留上一行的状态（长度 L-1 的结果）。
• 更优的算法（如马拉车算法）可达到 \(O(n)\) 时间复杂度，但区间 DP 是理解回文结构的经典方法。

核心代码框架（Java）

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;
    
    // 初始化长度为1的子串
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    
    // 遍历长度L从2到n
    for (int L = 2; L <= n; L++) {
        for (int i = 0; i <= n - L; i++) {
            int j = i + L - 1;
            if (s.charAt(i) == s.charAt(j)) {
                if (L == 2 || dp[i+1][j-1]) {
                    dp[i][j] = true;
                    if (L > maxLen) {
                        start = i;
                        maxLen = L;
                    }
                }
            }
        }
    }
    return s.substring(start, start + maxLen);
}