最长回文子串动态规划

最长回文子串问题可以使用动态规划来解决。

动态规划的思路是利用已知的子问题的解来求解更大规模的问题。对于回文串，我们可以定义一个二维数组 dp[i][j]，表示字符串从位置 i 到 j 是否是回文串。那么，如果 dp[i][j] = true，则表示从 i 到 j 的字符串是回文串。

根据回文串的定义，我们可以得到递推关系式：
- 如果 s[i] == s[j]，并且 s[i+1] 到 s[j-1] 是一个回文串，那么 s[i] 到 s[j] 也是一个回文串。即：如果 s[i] == s[j] 并且 j - i <= 2 或者 dp[i+1][j-1] = true，则 dp[i][j] = true。
- 如果 s[i] != s[j]，那么 s[i] 到 s[j] 不是一个回文串。即：如果 s[i] != s[j]，则 dp[i][j] = false。

根据递推关系式，我们可以使用动态规划的方式求解最长回文子串：
1. 初始化二维数组 dp 的对角线上的元素为 true，表示单个字符一定是回文串。
2. 从字符串的末尾开始遍历，从右下角开始计算 dp 数组的其他位置。
3. 根据递推关系式计算 dp 数组的其他位置。
4. 在计算过程中记录最长回文子串的起始位置和长度。
5. 根据最长回文子串的起始位置和长度截取原始字符串，即可得到最长回文子串。

下面是使用动态规划求解最长回文子串的代码示例（使用 Python 实现）：

def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1

    # 初始化对角线
    for i in range(n):
        dp[i][i] = True

    # 从右下角开始计算 dp 数组
    for i in range(n-1, -1, -1):
        for j in range(i+1, n):
            if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]):
                dp[i][j] = True
                if j - i + 1 > max_len:
                    max_len = j - i + 1
                    start = i

    return s[start:start+max_len]

这样，调用 `longestPalindrome` 函数并传入一个字符串，即可得到该字符串的最长回文子串。