#include <iostream> using namespace std; const int maxlen=1001; char str[maxlen]; int cost(int start,int tail)// 普通递归算法 { int x,y; if(start>=tail) return 0; if(str[start]==str[tail]) return cost(start+1,tail-1); x=cost(start+1,tail); y=cost(start,tail-1); if(x>y) return y+1; else return x+1; } int main() { while(scanf("%s",str)!=EOF) { int len; len=strlen(str); cout<<cost(0,len-1); } return 0; }

这段代码实现了一个字符串变为回文串的最小代价算法，使用了普通递归算法。但是，该算法的时间复杂度是指数级别的，对于较长的字符串会非常耗时。

如果想提高该算法的效率，可以使用动态规划或记忆化搜索。以下是使用动态规划的代码示例：

#include <iostream>
#include <cstring>
using namespace std;

const int maxlen = 1001;
char str[maxlen];
int dp[maxlen][maxlen];

int cost(int start, int tail) {
    if (dp[start][tail] != -1) return dp[start][tail]; // 如果已经计算过，直接返回结果
    if (start >= tail) return 0;
    if (str[start] == str[tail]) return dp[start][tail] = cost(start+1, tail-1); // 如果起始和结束位置的字符相等，直接把它们去掉
    int x = cost(start+1, tail); // 删除起始位置的字符
    int y = cost(start, tail-1); // 删除结束位置的字符
    return dp[start][tail] = min(x, y) + 1; // 返回删除一个字符后的最小代价
}

int main() {
    while (scanf("%s", str) != EOF) {
        int len = strlen(str);
        memset(dp, -1, sizeof(dp)); // 初始化为-1
        cout << cost(0, len-1) << endl;
    }
    return 0;
}

使用动态规划，我们可以避免重复计算，大大提高算法的效率。具体来说，我们使用一个二维数组dp来保存已经计算过的结果。数组的行表示字符串的起始位置，列表示字符串的结束位置。例如，数组元素dp[i][j]表示从字符串i到字符串j变为回文串的最小代价。

在计算dp[i][j]之前，我们先检查数组中是否已经保存了这个结果。如果已经保存了，就直接返回结果。如果没有保存，就按照正常算法计算dp[i][j]，并将结果保存到数组中。

这样，我们就可以避免重复计算，大大提高算法的效率。