【题意】：给出一个长度为n的字符串，问最少添加多少个字符可以使得修改后的字符串变成回文串。
【题解】：这题很容易想到用dp解。
最开始我用区间dp来解。
设状态dp[i][j]表示第i个字符到第j个字符所组成的字符串变成回文串所需添加字符的最少数目。
利用记忆化搜索，时间复杂度为O(n*n)，空间复杂度为O(n*n)。好吧，然后就无情地MLE了。
后面想到另外一个解法，求原字符串和逆序后字符串的LCS，然后答案就是n - LCS的长度，很容易证明其正确性。
这个解法时间复杂度也是O(n*n)，但是它可以利用滚动数组来压缩空间，然后问题就解决了。
【代码】：
区间dp的解法（MLE）：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 5050
6 const int inf = 1 << 30;
7 char str[maxn];
8 int n;
9 int dp[maxn][maxn];
10 int dfs(int i, int j) {
11 if(dp[i][j] != -1) return dp[i][j];
12 if(i >= j) return 0;
13 else {
14 int ans = inf;
15 if(str[i] == str[j]) ans = dfs(i + 1, j - 1);
16 ans = min(ans, dfs(i + 1, j) + 1);
17 ans = min(ans, dfs(i, j - 1) + 1);
18 return dp[i][j] = ans;
19 }
20 }
21
22 int main() {
23 while(~scanf("%d", &n)) {
24 scanf("%s", str);
25 memset(dp, -1, sizeof(dp));
26 int ans = dfs(0, n - 1);
27 printf("%d\n", ans);
28 }
29 return 0;
30 }
转化为LCS的解法（AC）：
1 #include "iostream"
2 #include "cstring"
3 #include "cstdio"
4 using namespace std;
5 #define maxn 5050
6 char s[maxn], t[maxn];
7 int n;
8 int dp[2][maxn];
9 void solve() {
10 for(int i = 0; i < n; i++) t[i] = s[n - 1 - i];
11 memset(dp, 0, sizeof(dp));
12 for(int i = 1; i <= n; i++) {
13 for(int j = 1; j <= n; j++) {
14 int idx = i % 2, idx2 = (i + 1) % 2;
15 if(s[i-1] == t[j-1]) dp[idx][j] = dp[idx2][j-1] + 1;
16 else dp[idx][j] = max(dp[idx2][j], dp[idx][j-1]);
17 }
18 }
19 printf("%d\n", n - dp[n%2][n]);
20 }
21
22 int main() {
23 while(~scanf("%d", &n)) {
24 scanf("%s", s);
25 solve();
26 }
27 return 0;
28 }
29