UVA 10617 Again Palindrome：區間 DP 計數回文子序列

問題描述

給定字符串，可刪除任意字符（也可不刪），求有多少種方式使剩餘字符形成回文串。空串不算回文。結果可能很大，需用 64 位整數。

DP 狀態定義

dp[i][j] = 子串 s[i..j] 中非空回文子序列的個數（i ≤ j）。

狀態轉移方程推導

情況 1：s[i] != s[j]

s[i..j] 的回文子序列 = s[i+1..j] 的 ∪ s[i..j-1] 的，但 s[i+1..j-1] 被重複計算了兩次：

dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

情況 2：s[i] == s[j]

除了上述並集，還有新增回文：

• 雙字符回文 "s[i]s[j]"
• 對每個 s[i+1..j-1] 的回文 X，兩側加上 s[i] 和 s[j] 形成新回文 "s[i] X s[j]"

新增數量 = dp[i+1][j-1] + 1，故：

dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1

（注意：此時 dp[i+1][j] + dp[i][j-1] 已包含 dp[i+1][j-1] 兩次，加 1 後恰好抵消減法）

完整代碼實現

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
const int MAXN = 100;
char s[MAXN];
ll dp[MAXN][MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%s", s);
        int len = strlen(s);
        // 初始化：長度 1
        for (int i = 0; i < len; ++i) dp[i][i] = 1;
        // 區間 DP：長度從 2 到 len
        for (int L = 2; L <= len; ++L) {
            for (int i = 0; i + L <= len; ++i) {
                int j = i + L - 1;
                if (s[i] == s[j])
                    dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1;
                else
                    dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
            }
        }
        printf("%lld\n", dp[0][len-1]);
    }
    return 0;
}

關鍵細節

1. 遍歷順序：按區間長度遞增，保證子問題已解決
2. 邊界條件：dp[i][i] = 1（單字符是回文）
3. 數據類型：長度 60 時結果可能達 2^60，必須用 long long
4. 空串處理：題目通常不計空串，初始化和轉移均遵循此約定

複雜度

• 時間：O(n²)，n ≤ 60 完全足夠
• 空間：O(n²)

常見變體

• 最長回文子序列長度：dp[i][j] = max(...)
• 最少插入次數構成回文：dp[i][j] = min(...)
• 回文分區最小切割數