POJ 1159 Palindrome：最少插入構造回文 = 長度 - LCS

核心結論

最少插入字符數 = 字符串長度 - 字符串與其逆序的最長公共子序列（LCS）長度。因為 LCS 對應已經對稱的部分，其餘字符需成對插入。

空間優化 DP

一維數組 dp[j] 表示前 i 字符與逆序前 j 字符的 LCS。滾動更新需保存 old = dp[j-1]（左上值）。

for (int i = 0; i < N; i++) {
    old = 0;
    for (int j = 0; j < N; j++) {
        temp = dp[j];
        if (s1[i] == s2[j]) dp[j] = old + 1;
        else dp[j] = max(temp, dp[j-1]);
        old = temp;
    }
}
printf("%d\n", N - dp[N-1]);

用 short 存儲 dp 節省內存（5000×5000 ≈ 25MB → 50MB 邊界）。注意僅單組測試數據。