记忆化搜索，$dp$。

$dp[L][R]$表示将区间$[L,R]$修改为一个回文串需要的最小代价。转移很容易写，区间$dp$或者记忆化搜索都可以。

区间$dp$：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char s[2010],op[5];int dp[2010][2010];int c[30][2];int m,n;int main(){    while(~scanf("%d%d",&m,&n))    {        scanf("%s",s);        for(int i=0;i
          
           =len) continue; if(x==2&&s[L]==s[R]) { dp[L][R]=0; continue; } if(s[L]==s[R]) dp[L][R] = min(dp[L][R],dp[L+1][R-1]); dp[L][R] = min(dp[L][R], dp[L+1][R]+c[s[L]-'a'][0]); dp[L][R] = min(dp[L][R], dp[L+1][R]+c[s[L]-'a'][1]); dp[L][R] = min(dp[L][R], dp[L][R-1]+c[s[R]-'a'][0]); dp[L][R] = min(dp[L][R], dp[L][R-1]+c[s[R]-'a'][1]); } } printf("%d\n",dp[0][n-1]); } return 0;}
          
         
        
       
      
     

记忆化搜索：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char s[2010],op[5];int dp[2010][2010];int c[30][2];int m,n,len;int dfs(int L,int R){    if(dp[L][R]!=0x7FFFFFFF) return dp[L][R];    if(R-L==0) dp[L][R]=0;    else if(R-L==1&&s[L]==s[R]) dp[L][R]=0;    else     {        int mn = 0x7FFFFFFF;        if(s[L]==s[R]) mn = min(mn,dfs(L+1,R-1));        mn = min(mn , dfs(L+1,R)+c[s[L]-'a'][0]);        mn = min(mn , dfs(L+1,R)+c[s[L]-'a'][1]);        mn = min(mn , dfs(L,R-1)+c[s[R]-'a'][0]);        mn = min(mn , dfs(L,R-1)+c[s[R]-'a'][1]);        dp[L][R] = mn;    }    return dp[L][R];}int main(){    while(~scanf("%d%d",&m,&n))    {        scanf("%s",s);        for(int i=0;i