题解 | #密码截取#

很经典的动态规划求最长回文串长度的问题

using namespace std;
int solve(string s){
    int res = 0;
    int length = s.size();
    if(length == 1) return 1;
    vector<vector<bool>>dp(length,vector<bool>(length,false));
    for(int i = 0;i<length;i++){
        dp[i][i] = true;
        if(i<length-1){
            if(s[i] == s[i+1]){
                dp[i][i+1] = true;
                res = 2;
            }
        }
    }//需要先将对角线(len==1)和长度为2的len的回文状态确定
    
    for(int len = 3;len<=length;len++){
        for(int i = 0;i+len-1<length;i++){
            int j = i+len-1;
            if(s[i] == s[j]&&(dp[i+1][j-1])){

                    dp[i][j] = true;
                    res = len;

            }
        }
    }

    return res;
}
int main(){
    string s;
    while(cin>>s){
        int result = solve(s);
        cout<<result<<endl;
    }

    return 0;
}