分析

本题是求最长回文子序列。
之后用总长度减去最长回文子序列长度即可。

求最长回文子序列：
$$设状态 f(i,j) 表示闭区间 [i, j] 的最长回文子序列长度集合。$$
f(i,j) 有两种状态转移:
$$若 s(i)==s(j)则 f(i,j)=f(i+1,j−1)+2$$ $$否则f(i,j)=max(f(i+1,j),f(i,j−1))$$
最终答案为 f(1,n)。(在区间[1,n]的最长回文子序列长度)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1E3+10;
string s;
int ans,f[N][N];
int main()
{
    cin>>s;
    if(s==string(s.rbegin(),s.rend()))  //如果本来就是回文串，直接输出0
    {
        cout<<0;
        return 0;
    }
    s=' '+s;    //s要让字符下标映射于[1~n]，可以在前面加一个' '
    int n=s.size();

    for(int len=1;len<=n;len++) //枚举序列长度len
    {
        for(int i=1;i+len-1<=n;i++) 
        {
            int j=i+len-1;
            if(len==1) f[i][j]=1;   //长度为1的字符串本身就是字符串
            else{
                f[i][j]=max(f[i+1][j],f[i][j-1]);
                if(s[i]==s[j]) f[i][j]=max(f[i][j],f[i+1][j-1]+2);
            }
            ans=max(ans,f[i][j]);
        }
    }
    cout<<n-ans-1;  //由于之前加了一个' '，要再减去' '的长度1
    return 0;
}