f[i][j]表示是使s[i]~s[j]变成回文串的最少添加字符数

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
char s[N];
int f[N][N];



int main()
{
    cin >> s;
    int n = strlen(s);
    for(int len = 1; len <= n; len ++)
    {
        for(int l = 0; l + len - 1 <= n; l ++)
        {
            int r = l + len - 1;
            f[l][r] = INF;
            if(s[l] == s[r]) f[l][r] = f[l + 1][r - 1];
            f[l][r] = min(f[l][r], min(f[l + 1][r] + 1, f[l][r - 1] + 1));
        }
    }

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

}