您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

2015 編程之美資格賽：回文子序列計數 DP 解法詳解

編輯：關於C語言

題目大意

給定字串，求其回文子序列個數（位置不同視為不同子序列）。答案對 100007 取模。字串長度 ≤ 1000，測資 ≤ 30 組。

例："aba" 的回文子序列有 "a" (位置0), "b", "a" (位置2), "aa", "aba" → 共 5 個。

區間型動態規劃

定義 dp[i][j] 為區間 [i, j] 內的回文子序列數（0 ≤ i ≤ j < n）。

狀態轉移

情況 1：s[i] == s[j]
新增以 s[i]、s[j] 為首尾的回文：
1. 單獨組成 "s[i]s[j]" (即 "aa") → +1
2. 包住中間 [i+1, j-1] 的所有回文 → +dp[i+1][j-1]
3. 加上左邊 [i, j-1] 與右邊 [i+1, j] 的回文
但 [i+1, j-1] 被重複計算了兩次，需扣除
合併： dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1
情況 2：s[i] != s[j]
合併左右區間，扣除重疊的中間區間：
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]

邊界條件

dp[i][i] = 1（單字元本身是回文）。

計算順序

按區間長度 len = 1 .. n-1 遞增，保證所需子問題已計算完畢。

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;

const int MOD = 100007;
const int MAXN = 1010;

int dp[MAXN][MAXN];
char s[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        cin >> s;
        int n = strlen(s);
        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < n; ++i) dp[i][i] = 1;

        for (int len = 1; len < n; ++len) {
            for (int i = 0; i + len < n; ++i) {
                int j = i + len;
                if (s[i] == s[j]) {
                    dp[i][j] = (dp[i][j-1] + dp[i+1][j] + 1) % MOD;
                } else {
                    dp[i][j] = (dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]) % MOD;
                    if (dp[i][j] < 0) dp[i][j] += MOD;
                }
            }
        }
        cout << "Case #" << tc << ": " << dp[0][n-1] % MOD << "\n";
    }
    return 0;
}