有一个字符串，你可以在任意位置添加任意字符，使其成为回文串。
问你最少需要添加多少个字符。
abcdc->abcdcba添加2个

简单分析：就是|s|-LCS(s, s1) s1为s的逆序字符串。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char a[1005], b[1005];
int f[1005][1005];

int main(){

    scanf("%s", a+1);
    int n=strlen(a+1);
    for(int i=1; i<=n; i++) b[n-i+1]=a[i];
    for(int i=1; i<=n; i++){
        f[i][0]=f[0][i]=0;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(a[i]==b[j]){
                f[i][j]=f[i-1][j-1]+1;
            }
            else{
                f[i][j]=max(f[i-1][j], f[i][j-1]);
            }
        }
    }
    printf("%d\n", n-f[n][n]);


    return 0;
}