题目链接：

题目大意：给定一串字符，添加最少的字符，使之成为回文串。

Sample Input

5Ab3bd

Sample Output

2 分析：这道题目之前有做过，就是将原字符串逆序得到另一个字符串，求它们的最长公共子序列，这样就能求得它的可以构成回文的最长字符数，用n减去即为添加最少可使之成为回文的数目。 可恨的是之前一直超内存，看了别人的解题报告，原来定义dp[MAX][MAX]时，不用int型，而是short型，内存只占int的一半（见上一篇日志） 另外逆序字符串可以不用新开一个数组，也可以直接在原数组上从后往前循环。 代码如下：

1 # include
     
       2 # include
      
        3  4 #define MAX 5005 5  6 int max(int a,int b,int c){ 7     int temp; 8     temp = a>b ? a :b; 9     return temp>c ?temp :c ;10 }11 char s[MAX],t[MAX];12 short dp[MAX][MAX];    //定义的类型为short13 14 int main(){15     int i,j,n;16     while(scanf("%d",&n)!=EOF){17         scanf("%s",s);18         for(i=0;i
      
     

 

另一种方法：dp[i][j]表示从第i个字符到第j个字符能构成的回文添加的最少字符。

1 #include 
     
       2 #define Min(a,b) (a
      
       0;i--)    //自底向上12         {    13             for(j=i+1;j<=lenth;j++)14             {15                 if(ch[i]==ch[j]){16                     dp[i][j] = dp[i+1][j-1];17                 }18                 else{19                     dp[i][j] = Min(dp[i+1][j],dp[i][j-1])+1;20                 }21             }22         }23         printf("%d\n",dp[1][lenth]);24     }25     return 0;26 }
      
     

 可是在某些变态的OJ里，上面的方法仍然不能AC，这是需要引入滚动数组优化空间，比如在第一种方法之上

代码如下：

1 # include
     
       2 # include
      
        3  4 #define MAX 5005 5  6 int max(int a,int b,int c){ 7     int temp; 8     temp = a>b ? a :b; 9     return temp>c ?temp :c ;10 }11 char s[MAX],t[MAX];12 short dp[2][MAX];13 14 int main(){15     int i,j,n;16     while(scanf("%d",&n)!=EOF){17         scanf("%s",s);18         for(i=0;i