A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome. As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
这个题目可以转化为求最长公共子串的问题，就是将原字符串逆转，然后求源字符串和逆转字符串的最长公公子串，可以在O(n^2)时间内求解.用原始字符串的长度减去最长公共子串的长度就是最少的操作数。
这个题目我给出了3种方法，本质起始都是一样的，第一个是递推解法，第二个是递归解法（无备忘，效率比较低），第三个递归求解，带备忘录，如果不考虑函数调用的时间，和递推解的时间代价差不多，都是O(n^2)：
//给定一个字符串，求对它最少进行多少次操作，可以变成一个回文串,递推解
void LSB(char *str,int n){
if(strlen(str)==0){
cout<<"empty string"<<endl;
return;
}
int **C=new int*[n];
for(int i=0;i<=n-1;i++){
C[i]=new int[n]();
}
//递归求解
//for(int k=0;k<=n-1;k++){
// for(int i=0;i<=n-1-k;i++){
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<=n-1;j++){
if(str[i]!=str[j])
C[i][j]=C[i+1][j]>C[i][j-1]?C[i][j-1]+1:C[i+1][j]+1;
else
C[i][j]=C[i+1][j-1];
}
}
cout<<C[0][n-1]<<endl;
//free mem
for(int i=0;i<=n-1;i++){
delete [] C[i];
}
delete [] C;
}
//给定一个字符串，求对它最少进行多少次操作，可以变成一个回文串,递归解（无备忘录版本）
int LCB_recur(char *str,int i,int j){
if(i>=j)
return 0;
if(str[i]==str[j]){
return LCB_recur(str,i+1,j-1);
}else{
int a=LCB_recur(str,i+1,j);
int b=LCB_recur(str,i,j-1);
return a>b?b+1:a+1;
}
}
///给定一个字符串，求对它最少进行多少次操作，可以变成一个回文串,递归解（备忘录版本）
int LCB_recur_mem(char *str,int n){
int **C=new int*[n];
for(int i=0;i<=n-1;i++){
C[i]=new int[n]();
}
//初始化
for(int i=0;i<=n-1;i++){
for(int j=0;j<=n-1;j++)
C[i][j]=INT_MAX;
}
return LCB_recur_memSub(C,str,0,n-1);
//free mem
for(int i=0;i<=n-1;i++){
delete [] C[i];
}
delete [] C;
}
int LCB_recur_memSub(int **C,char *str,int i,int j){
if(C[i][j]<INT_MAX)
return C[i][j];
if(i>=j)
C[i][j]=0;
else if(str[i]==str[j])
C[i][j]=LCB_recur_memSub(C,str,i+1,j-1);
else{
int a=LCB_recur_memSub(C,str,i+1,j);
int b=LCB_recur_memSub(C,str,i,j-1);
C[i][j]=a>b?b+1:a+1;
}
return C[i][j];
}