POJ 3280 區間動態規劃：最小成本構建回文串

題目大意

給定一個字串，允許插入或刪除字符，目標是將其轉換為回文串。每個字符的插入成本與刪除成本可能不同，實際操作時取兩者中的較小值。求達成目標所需的最小總成本。

核心思路

觀察可知，插入與刪除在本質上是等價的操作——若字符 str[i] == str[j]，則無需額外成本，直接轉移至內層子問題；否則需在「處理左端」與「處理右端」中取較小成本。

狀態定義與轉移方程

定義 dp[i][j] 為將子串 str[i..j] 轉為回文的最小成本。

• 若 str[i] == str[j]：dp[i][j] = dp[i+1][j-1]
• 否則：dp[i][j] = min(dp[i+1][j] + cost[str[i]-'a'], dp[i][j-1] + cost[str[j]-'a'])

採用區間 DP 自底向上填表，長度從 2 遞增至 len，最終答案為 dp[0][len-1]。

完整參考代碼 (C++)

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

const int INF = 0x3f3f3f3f;
const int MAXL = 2010;

int dp[MAXL][MAXL];
int cost[26];
char str[MAXL];

int main() {
    int n, len;
    while (~scanf("%d%d", &n, &len)) {
        scanf("%s", str);
        fill(cost, cost + 26, 0);
        for (int i = 1; i <= n; ++i) {
            char ch[2];
            int a, b;
            scanf("%s%d%d", ch, &a, &b);
            cost[ch[0] - 'a'] = min(a, b);
        }

        memset(dp, 0, sizeof(dp));
        for (int i = len - 1; i >= 0; --i) {
            for (int j = i + 1; j < len; ++j) {
                dp[i][j] = min(dp[i+1][j] + cost[str[i]-'a'],
                               dp[i][j-1] + cost[str[j]-'a']);
                if (str[i] == str[j])
                    dp[i][j] = min(dp[i][j], dp[i+1][j-1]);
            }
        }
        printf("%d\n", dp[0][len-1]);
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(len²)，len ≤ 2000 可在限制內通過。
• 空間複雜度：O(len²) 整型陣列，約 16 MB。

常見坑點提醒

• 輸入的字符成本行中，字符可能以字串形式讀入，需取 ch[0]。
• 成本取 min(insert, delete) 後再存入 cost[]，避免重複判斷。
• DP 邊界：dp[i][i] = 0（單字符本身即回文），dp[i][i-1] = 0（空串）。