题解 | #构造回文#

1. 把原来的序列倒过来。计算最长公共子序列。
2. 然后该字符串得长度减去最长公共子序列的长度即可。

#include<bits/stdc++.h>
using namespace std;

char a[1001], b[1001];
int dp[1001][1001];//公共最长子序列

int main(){
    string s;



    while(cin>>s){
       if(s.size()==1){
           cout<<0<<endl;
           continue;
       }

       for(int i = 0; i< s.size();i++){
           b[i] = s[s.size()-1-i];
       } 

       memset(dp,0,sizeof(dp));////清空数组

       for(int i = 1; i<=s.size();i++ ){
           for(int j = 1; j<= s.size();j++){
               if(s[i-1] == b[j-1]){
                   dp[i][j] = dp[i-1][j-1]+1;
               }else{
                   dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
               }
           }

       }

        cout<<s.size()-dp[s.size()][s.size()]<<endl;


    }


    return 0;
}