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

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

例如：

• 输入："babad"，输出："bab"或"aba"
• 输入："cbbd"，输出："bb"

解题过程

1. 问题分析
回文串具有对称性，判断一个子串是否为回文时：

• 长度为1的子串一定是回文
• 长度为2的子串需要两个字符相同
• 长度大于2的子串需要首尾字符相同，且去掉首尾后的子串也是回文

2. 状态定义
我们定义dp[i][j]表示子串s[i...j]是否为回文串（i ≤ j）：

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

3. 状态转移方程
根据回文串的性质，我们可以得到：

• 当i = j时：dp[i][j] = true（单个字符）
• 当j = i + 1时：dp[i][j] = (s[i] == s[j])（两个字符）
• 当j > i + 1时：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

4. 初始化
对于所有i = j的情况，dp[i][i] = true
其他情况初始化为false

5. 遍历顺序
由于dp[i][j]依赖于dp[i+1][j-1]（即左下方的状态），我们需要：

• 按子串长度从小到大遍历
• 先遍历所有可能的子串长度，再遍历起始位置

6. 记录结果
在填充dp表的过程中，我们记录：

• 当前找到的最长回文子串的起始位置和长度
• 或者直接记录最长回文子串本身

7. 详细实现步骤
让我们用"babad"作为例子来演示：

步骤1：初始化dp表（5×5矩阵，全部初始化为false）

  b a b a d
b F F F F F
a F F F F F  
b F F F F F
a F F F F F
d F F F F F

步骤2：处理长度为1的子串（都是回文）

对角线全部设为true

步骤3：处理长度为2的子串

• "ba": b≠a → false
• "ab": a≠b → false
• "ba": b≠a → false
• "ad": a≠d → false

步骤4：处理长度为3的子串

• "bab": b=b且"a"是回文 → true（新的最长回文）
• "aba": a=a且"b"是回文 → true（新的最长回文）
• "bad": b≠d → false

步骤5：处理长度为4的子串

• "baba": b≠a → false
• "abad": a≠d → false

步骤6：处理长度为5的子串

• "babad": b≠d → false

最终找到的最长回文子串是"bab"或"aba"。

8. 算法优化

• 时间复杂度：O(n²)
• 空间复杂度：O(n²)，可优化为O(n)
• 实际实现时，我们只需要记录当前最长回文子串的起始位置和长度

9. 代码框架

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    
    # 初始化长度为1的子串
    for i in range(n):
        dp[i][i] = True
    
    # 按子串长度遍历
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]
            else:
                dp[i][j] = False
            
            if dp[i][j] and length > max_len:
                start = i
                max_len = length
    
    return s[start:start + max_len]

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