动态规划

f[i][j]代表的是从字符串i到字符串j是否是回文

C++ 代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
    string str;
    getline(cin, str);
    int n = str.size(); 
    vector<vector<int>> f(n, vector<int>(n, false));
    int len = 0;
    for(int i = 0; i < n; i++){
        f[i][i] = true;
        for(int j = 0; j <= i; j++){
            if(str[i]==str[j] &&(i-j<=2||f[j+1][i-1]==true)) f[j][i] = true;
            if(f[j][i] && (i-j+1)> len) len = i-j+1;
        }
    }
    cout<<len<<endl;
    return 0;

}