刚开始真没看出来这是一道dp题。。

dp[i][j]表示i~j段修改成回文串所需的最少操作次数。然后根据s[i]和s[j]是否相等写出转移方程即可。

注意删除和插入操作其本质是一样的。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #define IO ios::sync_with_stdio(false);cin.tie(0); 9 #define INF 0x3f3f3f3f10 typedef long long ll;11 using namespace std;12 char s[110];13 int dp[110][110];14 int main()15 {16 while(cin >> s){17 int len = strlen(s);18 memset(dp, 0, sizeof(dp));19 for(int i = 0; i < len; i++){20 for(int j = i-1; j >= 0; j--){21 if(s[i] == s[j]){22 dp[j][i] = dp[j+1][i-1];23 }24 else {25 dp[j][i] = min(dp[j+1][i-1], min(dp[j+1][i], dp[j][i-1]))+1;26 }27 }28 }29 cout << dp[0][len-1] << endl;30 }31 return 0;32 }