最开始毫无头绪，然后参照了一位dalao的博客，思路是一个正序的字符串将其逆序，然后求最长公共子序列（LCS）,emm也属于动态规划。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int maxn = 1105; 8 char s1[maxn]; 9 char s2[maxn];10 11 int dp[maxn][maxn];12 13 int main(){14     cin >> s1;15     int len = strlen(s1);16     for (int i = 0,j = len - 1; i < len; i++,j--){17         s2[i] = s1[j];18     }19     memset(dp, 0, sizeof(dp));20     for (int i = 1; i <= len; i++){21         for (int j = 1; j <= len; j++){22             if (s1[i - 1] == s2[j - 1]){23                 dp[i][j] = max(dp[i - 1][j - 1] + 1, max(dp[i - 1][j], dp[i][j - 1]));24             }25             else{26                 dp[i][j] = max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1]));27             }28         }29     }30     cout << len - dp[len][len] << endl;31     return 0;32 }