这道题看了好大会没有思路，上网一搜发现这么简单，但是我为什么就想不到呢，？？就是求和它的逆序之后的字符串最长公共子序列，然后用总的长度减去它就行了。原因是是因为只要是在公共子序列里面，那么他就是对称的，少的那些就是需要补的

代码如下：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6  7 const int N = 1002; 8 int dp[N][N]; 9 int main()10 {11     int n;12     scanf("%d", &n);13     while (n--)14     {15         memset(dp, 0, sizeof(dp));16         string s1, s2;17         cin >> s1;18         int len = s1.length();19         for (int i = 0; i < len; i++)20             s2[i] = s1[len - i - 1];21         //求最长公共子序列22         for (int i = 1;i <= len; i++)23         {24             for (int j = 1; j <= len; j++)25             {26                 if (s1[i - 1] == s2[j - 1])27                     dp[i][j] = dp[i - 1][j - 1] + 1;28                 else29                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);30             }31         }32         printf("%d\n", len - dp[len][len]);33     }34 35     return 0;36 }