DP思路

原字符串添加x个字符变成回文序列，等价于，去掉x个字符变成回文序列,则问题转化为求最长回文子序列长度

#include<stdio.h>
#include<string.h>

char s[1010];
int f[1010][1010];

int max(int a,int b)
{
    if(a >= b) return a;
    else return b;
}

int main()
{
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    for(int len = 1;len <= n;len++)
    {
        for(int l = 1;l + len - 1 <= n;l++)
        {
            int r = l + len - 1;
            if(l == r) f[l][r] = 1;
            else
            {
                f[l][r] = f[l + 1][r - 1];
                f[l][r] = max(f[l+1][r],f[l][r-1]);
                if(s[l] == s[r]) f[l][r] = max(f[l][r],f[l+1][r-1] + 2);
            }
        }
    }
    printf("%d",n - f[1][n]);
    return 0;
}

踩过的坑

要先美剧长度，再枚举端点；
若先枚举左端点，再枚举右端点，会造成状态计算时所涉及的DP量为计算（~~大概是这个意思，表述不清）