POJ 1159 Palindrome：最少插入字符構成回文——LCS 變形 DP

POJ 1159 Palindrome：最少插入字符構成回文——LCS 變形 DP

題目大意

給定長度 N (≤5000) 的字符串，可在任意位置插入字符，求使其成為回文串的最少插入次數。

核心洞察：LCS 轉化

設原串為 S，反轉串為 S'。S 與 S' 的最長公共子序列 (LCS) 長度為 L。則答案 = N - L。

理由：LCS 對應的字符在原串中已按相對順序構成回文結構。其餘 N-L 個字符，只需在對稱位置插入對應字符即可構成完整回文。例如 "Ab3bd" 反轉 "db3bA"，LCS="b3b" (長度 3)，需插入 2 個字符（A 和 d）。

DP 遞推

dp[i][j] = (S[i-1] == S'[j-1]) ? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]);

空間優化：short 類型 + 滾動數組

N=5000，dp[5001][5001] 用 int 佔 100MB 可能 MLE。觀察到 LCS 長度 ≤ 5000，用 short (2 bytes) 佔 50MB 通常可過。或用兩行滾動數組 dp[2][5001] 降至 O(N) 空間。

完整代碼

#include 
#include 
#include 
using namespace std;
const int MAXN = 5005;
short dp[MAXN][MAXN]; // 關鍵：用 short 節省空間
char s[MAXN], rev[MAXN];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        scanf("%s", s);
        for (int i = 0; i < n; ++i) rev[i] = s[n-1-i];
        rev[n] = '\0';

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (s[i-1] == rev[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

        printf("%d\n", n - dp[n][n]);
    }
    return 0;
}

複雜度分析

• 時間：O(N^2) = 2.5×10^7 操作，C++ 1秒內可過。
• 空間：O(N^2) short 約 50 MB，符合 64MB 限制。

延伸

若需輸出具體回文串，可從 dp[n][n] 回溯構造。本題僅需最少插入數。