这道题是一道经典的dp，给定一个字符串 s，找到 s 中最长的回文子串。用dp[i][j]表示字符串s从i位到j位是回文子串。然后当每次赋值dp[i][j]=1的时候，记录回文子串的最大长度以及index。

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

1
2
3
4
5
6
7
8
9
示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string longestPalindrome(string s) {
    int len = s.length(), maxLen=0,left=0,right=s.length();
    int dp[1000+5][1000+5]={{0,},};
    for(int i=len-1;i>=0;i--){
        for(int j=i;j<len;j++){
            if(s[i]==s[j] && (j-i<=2 || dp[i+1][j-1])){
                dp[i][j]=1;
                if(maxLen<j-i+1){
                    maxLen=j-i+1;
                    left=i;
                    right=j;
                }
            }
        }
    }
    return s.substr(left,maxLen);
}