python用动态规划解法找到最长回文子串

动态规划是一种时间复杂度较低的解决方案，可以用于求解最长回文子串。

1. 定义状态

定义一个二维数组dp，其中dp[i][j]表示i到j的子串是否为回文子串。

2. 状态转移方程

当dp[i+1][j-1]为回文且s[i]==s[j]时，说明dp[i][j]也是回文。即：

dp[i][j] = dp[i+1][j-1] and s[i]==s[j]

当i=j时，dp[i][j]必为回文。

当j-i=1且s[i]==s[j]时，dp[i][j]也必为回文。

3. 初始化

将所有长度为1的子串初始化为回文，即dp[i][i]=True。

4. 遍历顺序

按照子串长度从小到大，从左到右遍历，即先遍历长度为2的子串，再遍历长度为3的子串，以此类推。

5. 返回结果

在遍历过程中，记录最长的回文子串即可。

下面是Python的代码实现：

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

    dp = [[False] * n for _ in range(n)]
    max_len = 1
    start = 0

    for i in range(n):
        dp[i][i] = True

    for j in range(1, n):
        for i in range(j):
            if s[i] == s[j]:
                if j - i < 3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]
            else:
                dp[i][j] = False

            if dp[i][j]:
                cur_len = j - i + 1
                if cur_len > max_len:
                    max_len = cur_len
                    start = i

    return s[start:start + max_len]

上面的代码中，我们用max_len和start记录最长回文子串的长度和起始位置，遍历过程中更新这两个变量即可。