给一个字符串，求插入最少的字符使之成为回文，回文就是顺着读和逆着读是一样的。。。
针对这个性质，把一个字符串化为两个，一个顺着，一个逆着，然后找一次最长公共子序列，插入的最少字符数即为字符串的长度-最长公共子序列的长度。
另一种做法（我自己想太多），是从2序列比对中找的灵感，和最长公共子序列的做法差不多，但是效果不好，2序列比对可用来解再复杂一点点的问题会更好。。。2序列比对，中间有插入，删除，替换三种操作，给每种操作（比对）赋予代价值。。求两个序列的最优比对值
照抄《算法设计与分析导论》中P140
转移方程为见代码中的注释：
贴代码：
先贴LCS的代码：
View Code
1 #include <cstdio> 2 #include <cstring> 3 #define N 5005 4 char a[N]; 5 int d[2][N]; 6 int max(int x,int y) 7 { 8 return x>y?x:y; 9 } 10 int main() 11 { 12 int i,j; 13 int n; 14 // freopen("in.cpp","r",stdin); 15 while(~scanf("%d",&n)) 16 { 17 scanf("%s",a); 18 for(i=0; i<=n; ++i) 19 d[0][i] = 0; 20 d[1][0] = 0; 21 int x=1; 22 for(i=1; i<=n; ++i) 23 { 24 for(j=1; j<=n; ++j) 25 { 26 if(a[i-1] == a[n-j]) 27 d[x][j] = d[1-x][j-1]+1; 28 else 29 d[x][j] = max(d[1-x][j],d[x][j-1]); 30 } 31 x = 1-x; //实现滚动，原来为0，现在为1，原来为1，现在为0 32 } 33 printf("%d\n",n-d[1-x][n]);//输出最后结果 34 } 35 return 0; 36 }
再贴2序列比对：都用了滚动数组
View Code
1 #include <cstdio> 2 #define N 5005 3 #define INF 1000000000 4 int A[2][N];//A[i][j]表示字符串a1,a2,```,ai与字符串b1,b2,```,bj的最少插入 5 char s[N]; 6 int f(char a,char b) 7 { 8 if(a == b) return 0; //a,b相等为0 9 else return -INF;//a,b不等为负无穷，因为该题只能插入 10 //不能替换，还有插入删除的代价为-1，插入删除是对称的，在这里 11 } 12 int max(int x,int y)//求两个数的最大值 13 { 14 return x>y?x:y; 15 } 16 int main() 17 { 18 // freopen("in.cpp","r",stdin); 19 int n,i,j; 20 while(scanf("%d",&n) != EOF) 21 { 22 scanf("%s",s); 23 for(i=1; i<=n; ++i)//初始化,都是插入 24 A[0][i] = -i; 25 A[0][0] = 0; 26 bool x=1; 27 A[x][0] = -1; 28 for(i=1; i<=n; ++i) 29 { 30 for(j=1; j<=n; ++j) 31 { 32 A[x][j] = max(A[!x][j]-1,A[x][j-1]-1);//2个状态转移方程 33 A[x][j] = max(A[x][j],A[!x][j-1] + f(s[i-1],s[n-j])); 34 } 35 x = !x; 36 A[x][0] = A[!x][0]-1; 37 } 38 printf("%d\n",-A[!x][n]/2);//因为翻倍计算了，最后结果得除以2 39 } 40 return 0; 41 }