反向 LCS
因為找到反向字串與原字串的 LCS ，就代表找到原字串中，最長的回文子序列， 將這個 LCS 長度減去原字串長 == 最少要插入的字元，使得整個字串變成回文。
需要留意記憶體大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#pragma GCC optimize("O3")
#pragma GCC target ("avx")
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
unsigned short dp[2][5010]; // 滾動陣列
int N;
string s;
inline int solv() {
memset(dp, 0x00, sizeof(dp));
for (int i=1; i<=N; ++i) {
for (int j=1; j<=N; ++j) {
if (s[i-1]==s[N-j]) dp[i&1][j] = dp[(i-1)&1][j-1]+1;
else {
dp[i&1][j] = max(dp[(i-1)&1][j], dp[i&1][j-1]);
}
}
}
return N-(int)max(dp[1][N],dp[0][N]);
}
int main(void) {
cin >> N;
cin >> s;
cout << solv() << endl;
return 0;
}