基本可以确定这道题是一个dp，我首先想到的思路是，根据回文序列对称的特性，把这个原序列分成前后两半来做，但是每次对序列进行添加操作，都会导致中心点的移动，导致这种做法非常麻烦，因此需要转换思路：
不妨直接把整个序列颠倒过来，那些本身是回文串的部分，颠倒之后还是回文串，而剩下的那些部分，为了把它们变成回文串，就需要在原序列的对称位置，添加相同字母，则答案就是
len(原)-len(最大回文子串)
而len(最大回文字串)=原序列和颠倒后序列的最长公共子序列长度,即LCS
代码如下:
#include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> #define For(i, j, n) for(int i = j ; i <= n ; ++i) using namespace std; const int N = 1005; char str[N], ctr[N]; int f[N][N]; int main() { cin >> str; int len = strlen(str); for(int i = 0; i < len; i++) ctr[len - 1 - i] = str[i]; for(int i = 0; i < len; i++) for(int j = 0; j < len; j++) { if(str[i] == ctr[j]) { if(i < 1 || j < 1) f[i][j] = 1; else f[i][j] = f[i - 1][j - 1] + 1; } else { int a = (i < 1) ? 0 : f[i - 1][j], b = (j < 1) ? 0 : f[i][j - 1]; f[i][j] = max(a, b); } } cout << len - f[len - 1][len - 1]; return 0; }