最长回文子串（动态规划解法）

让我为您详细讲解最长回文子串问题的动态规划解法。

问题描述
给定一个字符串s，找到s中最长的回文子串。回文串是正着读和反着读都一样的字符串。

示例
输入：s = "babad"
输出："bab" 或 "aba"

解题思路

步骤1：定义状态
我们定义dp[i][j]表示字符串s从索引i到索引j的子串是否是回文串。

• 如果dp[i][j] = true，表示s[i...j]是回文串
• 如果dp[i][j] = false，表示s[i...j]不是回文串

步骤2：状态转移方程
对于任意子串s[i...j]，判断它是否是回文串需要满足：

1. 两端的字符相等：s[i] == s[j]
2. 去掉两端字符后的子串是回文串（或者子串长度≤2）

状态转移方程：

• 当j - i ≤ 2时（即子串长度为1、2或3）：
  dp[i][j] = (s[i] == s[j])
• 当j - i > 2时：
  dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

步骤3：初始化

• 单个字符一定是回文串：dp[i][i] = true
• 长度为2的子串：dp[i][i+1] = (s[i] == s[i+1])

步骤4：遍历顺序
由于dp[i][j]依赖于dp[i+1][j-1]（即左下角的值），我们需要：

• 按子串长度从小到大遍历
• 先遍历子串长度，再遍历起始位置

步骤5：记录结果
在填充dp表的过程中，记录最长回文子串的起始位置和长度。

详细实现过程

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    
    # 初始化dp表
    dp = [[False] * n for _ in range(n)]
    
    # 初始化：所有长度为1的子串都是回文串
    for i in range(n):
        dp[i][i] = True
    
    max_len = 1  # 记录最长回文子串长度
    start = 0    # 记录最长回文子串起始位置
    
    # 先处理长度为2的子串
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            max_len = 2
            start = i
    
    # 按子串长度从小到大遍历（从长度3开始）
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1  # 子串结束位置
            
            # 状态转移
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                
                if length > max_len:
                    max_len = length
                    start = i
    
    return s[start:start + max_len]

逐步分析示例 s = "babad"

1. 初始化：

   • dp[0][0] = dp[1][1] = dp[2][2] = dp[3][3] = dp[4][4] = True
   • 所有长度为1的子串都是回文串

2. 处理长度为2的子串：

   • "ba": dp[0][1] = False
   • "ab": dp[1][2] = False
   • "ba": dp[2][3] = False
   • "ad": dp[3][4] = False
   • 当前最长："b" 或 "a" 等（长度为1）

3. 处理长度为3的子串：

   • "bab": dp[0][2] = (s[0]=='b'==s[2]=='b') && dp[1][1]=True → True
     • 更新最长：start=0, max_len=3 → "bab"
   • "aba": dp[1][3] = (s[1]=='a'==s[3]=='a') && dp[2][2]=True → True
     • 同样长度为3，也是有效答案
   • "bad": dp[2][4] = (s[2]=='b'≠s[4]=='d') → False

4. 处理长度为4的子串：

   • "baba": dp[0][3] = (s[0]=='b'≠s[3]=='a') → False
   • "abad": dp[1][4] = (s[1]=='a'≠s[4]=='d') → False

5. 处理长度为5的子串：

   • "babad": dp[0][4] = (s[0]=='b'≠s[4]=='d') → False

最终结果：最长回文子串是"bab"或"aba"

复杂度分析

• 时间复杂度：O(n²)，需要填充n×n的dp表
• 空间复杂度：O(n²)，用于存储dp表

这种方法通过动态规划系统地检查所有可能的子串，确保找到最长的回文子串。