(区间dp)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=1010;
int f[N][N];//左端点l右端点r的区间中 最长回文子串的长度
string s;
int main()
{
    cin>>s;
    n=s.size();
    for(int len=1;len<=n;len++)//区间dp类似石子合并
    {
        for(int l=0;l+len-1<n;l++)//枚举左端点
        {
            int r=l+len-1;
            if(len==1) f[l][r]=1;//左右端点相等时回文子串长度为1
            else
            {
            if(s[l]==s[r]) f[l][r]=f[l+1][r-1]+2;// l, r 均在区间 [l, r] 之中
            else
                f[l][r]=max(f[l][r],max(f[l+1][r],f[l][r-1]));
                //l在区间 [l, r] 之中, f[l][r] = f[l, r - 1]
           // r在区间 [l, r] 之中, f[l][r] = f[l + 1, r]
            //l, r均不在区间 [l, r] 之中 f[l][r] = f[l + 1][r - 1]
            }
        }
    }

    cout<<n-f[0][n-1]<<endl;
    return 0;
}