C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int f[N][N];
char s[N];
int main()
{
scanf("%s", 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;
if (len == 1)f[l][r] = 1;//初始化
else
{
if (s[l] == s[r])f[l][r] = f[l + 1][r - 1] + 2;
if (f[l][r - 1] > f[l][r])f[l][r] = f[l][r - 1];
if (f[l + 1][r] > f[l][r])f[l][r] = f[l + 1][r];
}
}
cout << n - f[0][n - 1] << endl;
}