题目链接：

题目大意：

题意很明确，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。

解题思路：

设原序列S的逆序列为S'

最少需要补充的字母数 = 原序列S的长度 —  S和S'的最长公共子序列长度

采用滚动数组节省空间

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int maxn = 1e4 + 10; 7 char s1[maxn], s2[maxn]; 8 int dp[2][maxn], n; 9 int main()10 {11     scanf("%d", &n);12     scanf("%s", s1);13     for(int i = 0; i < n; i++)14         s2[i] = s1[n - 1 - i];15     for(int i = 0; i < n; i++)16     {17         for(int j = 0; j < n; j++)18         {19             int now = (i + 1) & 1;20             if(s1[i] == s2[j])21                 dp[now][j + 1] = dp[!now][j] + 1;22             else dp[now][j + 1] = max(dp[!now][j + 1], dp[now][j]);23         }24     }25     cout<