POJ 1159：Palindrome - 最少插入構造回文 (DP + 滾動數組)

問題描述

給定長度 N ≤ 5000 的字符串，求最少插入幾個字符使其成為回文串。等價於：N - LCS(s, reverse(s))，即最長公共子序列 (LCS) 長度。

DP 定義

dp[i][j]：s[1..i] 與 rev[1..j] 的 LCS 長度。

轉移：

• s[i] == rev[j]：dp[i][j] = dp[i-1][j-1] + 1
• 否則：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

滾動數組優化空間

因 dp[i][*] 僅依賴 dp[i-1][*] 和 dp[i][j-1]，可用兩行數組交替：dp[2][N+1]，索引 i%2。

代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
char s[MAXN], rev[MAXN];
short dp[2][MAXN]; // short 足夠存 5000，節省內存

int main() {
    int n;
    while (cin >> n) {
        cin >> (s+1);
        for (int i = 1; i <= n; ++i) rev[n-i+1] = s[i];
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i) {
            int cur = i & 1, pre = cur ^ 1;
            for (int j = 1; j <= n; ++j) {
                if (s[i] == rev[j]) dp[cur][j] = dp[pre][j-1] + 1;
                else dp[cur][j] = max(dp[pre][j], dp[cur][j-1]);
            }
        }
        cout << n - dp[n&1][n] << '\n';
    }
    return 0;
}

關鍵點

• LCS 等價於最長回文子序列 (LPS)。
• 滾動數組將空間從 O(N^2) 降至 O(N)，避免 MLE。
• 用 short (2 bytes) 存儲 DP 值，進一步減半內存。

總結

經典「最少插入構造回文」轉化為 LCS 問題，滾動數組優化空間是大數據範圍下的關鍵技巧。