演算法題：刪除數字構成最長回文數，雙指針或動態規劃求解

問題描述

給定數字字串（如 "1234564321"），刪除任意字元（不改變相對順序），構成最長回文子序列。

範例分析

1234564321 長度 10，中心對稱。刪除 5 或 6 即得 123464321 或 12354321，長度 9 為最長回文。

演算法：動態規劃 O(n²)

int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector> dp(n, vector(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
            else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    }
    return dp[0][n-1];
}

輸出實際回文串

回溯 dp 表或使用 string 版 DP 直接構建結果。

複雜度

• 時間 O(n²)，空間 O(n²)（可優化至 O(n) 空間）。
• n ≤ 5000 時建議 Manacher 算法（僅適用連續子串，本題為子序列）。