UVA 10739 String to Palindrome：編輯距離動態規劃求最少操作數

題目大意

給定字符串，允許三種操作：插入、刪除、替換（每操作代價 1）。求將其變為回文字符串的最少操作數。長度 ≤ 1000。

動態規劃模型

狀態定義

dp[i][j]：將子串 s[i..j] 變為回文的最少操作數。

轉移方程

• 若 s[i] == s[j]：dp[i][j] = dp[i+1][j-1]（兩端匹配，無需操作）。
• 否則取三種操作最小值 +1：
  　　dp[i][j] = min(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) + 1
  　　- dp[i+1][j]：刪除 s[i] 或在 j 後插入 s[i]
  　　- dp[i][j-1]：刪除 s[j] 或在 i 前插入 s[j]
  　　- dp[i+1][j-1]：替換 s[i] 或 s[j] 使其匹配

填表順序

按區間長度遞增，或 i 從後向前、j 從前向後。邊界：dp[i][i] = 0（單字符本身回文）。

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
char s[N];
int dp[N][N];
int main() {
    int T, Case = 1;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s);
        int len = strlen(s);
        memset(dp, 0, sizeof(dp));
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1];
                else dp[i][j] = min({dp[i+1][j], dp[i][j-1], dp[i+1][j-1]}) + 1;
            }
        }
        printf("Case %d: %d\n", Case++, dp[0][len-1]);
    }
    return 0;
}

複雜度分析

• 時間：O(n²)，n ≤ 1000 → 10⁶ 操作，極快。
• 空間：O(n²) 整型數組 ≈ 4MB，可接受。可優化至 O(n)（只需保留下一行）。

關鍵點

• 插入、刪除、替換在回文問題中對稱等價，統一為三種子問題取最小。
• 初始化 dp[i][i]=0，dp[i][i+1] = (s[i]==s[i+1]?0:1) 隱含在循環中。
• 多測試用例，注意清空 dp 數組。