题解 | #最长回文子串#

using namespace std;

//动态规划之区间DP
int dp[1000][1000];
int main()
{
    string str;
    getline(cin,str);
    int num=str.size(),temp=1;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<num;i++){
        dp[i][i]=1;
        if(i<num-1){
            if(str[i]==str[i+1]){
                dp[i][i+1]=1;
                temp=2;
            }
        }
    }
    //状态转移方程
    for(int j=3;j<=num;j++)
        for(int i=0;i+j-1<num;i++){
            int m=i+j-1;
            if(str[i]==str[m]&&dp[i+1][m-1]==1){
                dp[i][m]=1;
                temp=j;
            }
        }
    cout<<temp<<endl;
    return 0;
}