[数据结构与算法]最长回文子串（动态规划算法）

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

提示：
- 1 <= s.length <= 1000
- s 仅由数字和英文字母（大写和/或小写）组成

暴力解法时间复杂度为O(n^3)，下面给出动态规划解法，时间复杂度为O(n的2次方)。也可以用中心扩散法，中心扩散法的时间复杂度也为O(n的2次方).

class Solution {
public:
    //时间复杂度为O(n^2)
    string longestPalindrome(string s) {

        int n=s.length();
        bool dp[n+1][n+1];//d[i][j]表示[i,j]是否为回文串
        int maxlen=1,idx=0;

        if(n<2) //如果长度小于2，就是回文串，直接返回原字符串
            return s;

        for(int i=0;i<=n;i++)
            dp[i][i]=true; //dp数组初始化，对角线元素都初始化为true

        for(int j=1;j<n;j++){
            for(int i=0;i<j;i++){

                if(s[i]!=s[j]){ //如果两边字符不相等，则不为回文串
                    dp[i][j]=false;
                }else{ //边界条件
                    if(j-i<3){ //如果两边元素相等去掉两边的字符剩下一个字符或者没有字符，即字符串长度等于2或者3，则为回文串
                        dp[i][j]=true;
                    }else{ //如果两边元素相等且字符串长度大于3，则依据里面子串是否为回文串判断当前字符串是否为回文串
                        dp[i][j]=dp[i+1][j-1];
                    }
                }

                 if(dp[i][j]&&j-i+1>maxlen){
                    maxlen=j-i+1; //记录回文串的最大长度
                    idx=i; //记录回文串的开始下标
                }

            }
        }

        return s.substr(idx,maxlen); //返回最长回文串
    }
};