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

给你一个字符串?s，找到?s?中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

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

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        if n<2:
            return s
        
        max_len=1
        begin=0
        #dp[i][j]表示s[i..j]是否是会问串
        dp=[[False]*n for _ in range(n)]
        for i in range(n):
            dp[i][i]=True

        #递推开始
        #先枚举子串长度
        for L in range(2,n+1):
            #枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                #有L和i可以确定有边界，即j-i+1=L得
                j=L+i-1
                #如果有边界越界，就可以退出当前循环
                if j>=n:
                    break

                if s[i]!=s[j]:
                    dp[i][j]=False
                else:
                    if j-i<3:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                #只要的dp[i][L]==true成立，就表示子串s[i..L]是会问，此时记录会问长度和起始位置
                if dp[i][j] and j-i+1>max_len:
                    max_len=j-i+1
                    begin=i
        return s[begin:begin+max_len]