题目分析

得到最少的脱落数目，等价于求求最少的单个字符（无回文匹配的字符），那麽也就是求最大的回文字符数
然后由总长度减去最大回文字符数就是答案

注意下图右下角应该是 f[i+1][j-1]+2(s[i]==s[j])

闫氏dp法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int f[N][N];
char str[N];
int main()
{
    cin>>str+1;
    int n = strlen(str+1);
    for(int len=1;len<=n;++len)
    {
        for(int i=1;i+len-1<=n;++i)
        {
            int j = i+len-1;
            if(len==1){f[i][j]=1;continue;}
            f[i][j]=max(f[i+1][j],f[i][j-1]);
            if(str[i]==str[j])
                f[i][j]=max(f[i+1][j-1]+2,f[i][j]);
        }
    }
    cout<<n-f[1][n]<<endl;
    return 0;
}