给一个字符串

可以再任意位置添加或删除字母（给出花费的） 使得字符串变成回文

思路：

其实添加和删除的性质是一样的

添加一个字母和删去相对应的字母 对于使原文变成回文

的贡献是一样的 所以我们取花费的时候 只取小的花费

为了理解方面统一用删除吧

从两端进行遍历

1 如果对应相等 则直接去掉就可以  （无需花费）

2 如果只有一个字符了 直接去掉 （无需花费）

3 否则选择删掉左边 和 删掉右边 两种情况中最优的（只有给出花费才能删）

代码及其注释：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=2005;char s[N];int cost[27];int ans[N][N];//在l 到 r 区间变成回文的最小花费int dp(int l,int r){    if(ans[l][r]!=-1)//记忆化搜索    return ans[l][r];    if(l==r)//只有一个字符    {        ans[l][r]=0;        return ans[l][r];    }    if(s[l]==s[r])//左右相等    {        if(l+1==r)        ans[l][r]=0;        else        ans[l][r]=dp(l+1,r-1);        return ans[l][r];    }    ans[l][r]=min(cost[s[l]-'a']+dp(l+1,r),dp(l,r-1)+cost[s[r]-'a']);//两种情况选最优    return ans[l][r];}int main(){   int n,m;   while(scanf("%d %d",&n,&m)!=EOF)   {       scanf("%s",s);       memset(cost,-1,sizeof(cost));       while(n--)       {           char c;           int v1,v2;           getchar();           scanf("%c %d %d",&c,&v1,&v2);           cost[c-'a']=min(v1,v2);       }       memset(ans,-1,sizeof(ans));       printf("%d\n",dp(0,m-1));   }   return 0;}