POJ 1159 Palindrome：最長公共子序列 + 滾動數組優化空間

問題轉化

在字符串中插入最少字符使其成為回文 ⇔ 求字符串與其逆序的 最長公共子序列 (LCS) 長度 L，答案 = n - L。

標準 LCS 遞推

if (a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

空間優化：滾動數組

dp[i][j] 只依賴 i-1 行，用 dp[2][N] 交替：

int dp[2][5001];
for (int i = 1; i <= n; i++) {
    int cur = i & 1, prev = cur ^ 1;
    for (int j = 1; j <= n; j++) {
        dp[cur][j] = max(dp[cur][j-1], dp[prev][j]);
        if (a[i] == b[j])
            dp[cur][j] = max(dp[cur][j], dp[prev][j-1] + 1);
    }
}
int L = dp[n & 1][n];

兩種優化方案對比

完整代碼（滾動數組版）

#include <cstdio>
#include <algorithm>
using namespace std;

int a[5001], b[5001], dp[2][5001];

int main() {
    int n; scanf("%d", &n); getchar();
    for (int i = 1; i <= n; i++) {
        char c; scanf("%c", &c);
        a[i] = b[n-i+1] = c;
    }
    for (int i = 1; i <= n; i++) {
        int cur = i & 1, prev = cur ^ 1;
        for (int j = 1; j <= n; j++) {
            dp[cur][j] = max(dp[cur][j-1], dp[prev][j]);
            if (a[i] == b[j])
                dp[cur][j] = max(dp[cur][j], dp[prev][j-1] + 1);
        }
    }
    printf("%d\n", n - dp[n & 1][n]);
    return 0;
}