本文共 458 字，大约阅读时间需要 1 分钟。

题意：给你一个字符串，问最少加多少个字符可以使之成为回文串。

思路：把字符串倒置 ， 求最长公共子序列， 字符长度 减 最长公共子序列长度就是 结果。

            注意： 卡内存， 需要用 01 数组。

代码：

#include
   
    #include
    
     int dp[2][5010]; // 01 数组， 节约内存int max(int a,int b){    if(a>b)        return a;    return b;}int main( ){    char str[5010], str1[5010];    int n,i,j;    scanf("%d ",&n);  // 字符串长度    scanf("%s",str); // 字符串    j=0;    for(i=n-1; i>=0; i--)        str1[j++] = str[i];  // 倒置    memset(dp,0,sizeof(dp)); // 初始化    for(i=0; i