题解

可使用最长公共子序列解决这个问题（线性dp）：

#include<bits/stdc++.h>
using namespace std;
int dp[1002][1002];
string s1,s2;
int main(){
    cin>>s1;
    s2=s1;
    reverse(s1.begin(),s1.end());
    for(int i=1;i<=s1.size();i++){
        for(int j=1;j<=s2.size();j++){
            if(s1[i-1]==s2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int len=dp[s1.size()][s2.size()];
    cout<<s1.size()-len;
    return 0;
}