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

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

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

输入：s = "cbbd"
输出："bb"

解题思路
我们可以使用动态规划来解决这个问题。定义dp[i][j]表示子串s[i...j]是否为回文串。

状态转移方程

1. 当子串长度为1时：dp[i][i] = true（单个字符一定是回文）
2. 当子串长度为2时：dp[i][i+1] = (s[i] == s[i+1])（两个相同字符是回文）
3. 当子串长度大于2时：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

详细步骤

步骤1：初始化
创建一个二维dp数组，dp[i][j]表示s[i...j]是否为回文串。
初始化所有长度为1的子串为回文：

n = len(s)
dp = [[False]*n for _ in range(n)]

# 所有单个字符都是回文
for i in range(n):
    dp[i][i] = True

步骤2：处理特殊情况
记录最长回文子串的起始位置和长度：

start = 0      # 最长回文子串起始位置
max_len = 1    # 最长回文子串长度

步骤3：遍历所有可能的子串长度
我们从长度为2的子串开始，逐渐增加子串长度：

for L in range(2, n+1):    # L表示当前检查的子串长度
    for i in range(n-L+1):  # i表示子串起始位置
        j = i + L - 1       # j表示子串结束位置
        
        if L == 2:  # 长度为2的子串
            if s[i] == s[j]:
                dp[i][j] = True
                if L > max_len:
                    start = i
                    max_len = L
        else:       # 长度大于2的子串
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                if L > max_len:
                    start = i
                    max_len = L

步骤4：返回结果
根据记录的起始位置和长度返回最长回文子串：

return s[start:start+max_len]

完整代码示例

def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s
    
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    
    # 初始化：所有单个字符都是回文
    for i in range(n):
        dp[i][i] = True
    
    # 检查所有可能的子串长度
    for L in range(2, n+1):
        for i in range(n-L+1):
            j = i + L - 1
            
            if L == 2:
                if s[i] == s[j]:
                    dp[i][j] = True
                    if L > max_len:
                        start = i
                        max_len = L
            else:
                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    if L > max_len:
                        start = i
                        max_len = L
    
    return s[start:start+max_len]

复杂度分析

• 时间复杂度：O(n²)，需要填充n×n的dp表
• 空间复杂度：O(n²)，需要n×n的二维数组存储dp状态

优化思路
对于这个问题，还可以使用中心扩展法将空间复杂度优化到O(1)，但动态规划解法思路更直观，易于理解和实现。