【題意】：給出一個(gè)長度為n的字符串，問最少添加多少個(gè)字符可以使得修改后的字符串變成回文串。
【題解】：這題很容易想到用dp解。
最開始我用區(qū)間dp來解。
設(shè)狀態(tài)dp[i][j]表示第i個(gè)字符到第j個(gè)字符所組成的字符串變成回文串所需添加字符的最少數(shù)目。
利用記憶化搜索，時(shí)間復(fù)雜度為O(n*n)，空間復(fù)雜度為O(n*n)。好吧，然后就無情地MLE了。
后面想到另外一個(gè)解法，求原字符串和逆序后字符串的LCS，然后答案就是n - LCS的長度，很容易證明其正確性。
這個(gè)解法時(shí)間復(fù)雜度也是O(n*n)，但是它可以利用滾動(dòng)數(shù)組來壓縮空間，然后問題就解決了。
【代碼】：
區(qū)間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 }
轉(zhuǎn)化為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