POJ 1159 Palindrome（最長回文子序列 LCS 轉化）

POJ 1159 Palindrome - 最長回文子序列

求字符串中最長回文子序列長度，答案 = n - LPS 長度。兩種方法：直接 DP 或轉化為 LCS。

方法一：直接 DP（右上三角填表）

dp[i][j] = s[i..j] 的 LPS 長度。只需維護兩行滾動數組。

// 狀態壓縮：tbl[2][MAX_N]
for (d = 2; d <= len; d++) {
    id = !id;
    for (i = 0, j = i+d-1; j < len; i++, j++) {
        if (s[i] == s[j] && d == 2) tbl[id][i] = 2;
        else if (s[i] == s[j]) tbl[id][i] = tbl[id][i+1] + 2;
        else tbl[id][i] = max(tbl[!id][i], tbl[!id][i+1]);
    }
}
return tbl[id][0];

方法二：轉化為 LCS（更直觀）

LPS(s) = LCS(s, reverse(s))。同樣用滾動數組優化空間。

// 經典 LCS DP
for (i = 0; i < len; i++) {
    id = !id;
    for (j = 0; j < len; j++) {
        if (s[i] == rev[j]) tbl[id][j+1] = tbl[!id][j] + 1;
        else tbl[id][j+1] = max(tbl[!id][j+1], tbl[id][j]);
    }
}
return tbl[id][len];

完整代碼對比

關鍵優化：空間壓縮

n ≤ 5000，二維數組 5000² × 2B = 50MB 超限。必須用滾動數組 tbl[2][5001]。

複雜度分析

• 時間：O(n²) = 25M 操作，1秒內可行
• 空間：O(n) = 10KB