POJ 3356 AGTC：經典動態規劃求最小編輯距離

POJ 3356 AGTC：經典動態規劃求最小編輯距離

給定兩個 DNA 序列 X, Y（長度 ≤ 1000），允許三種操作：刪除一字符、插入一字符、替換一字符。求將 X 轉化為 Y 的最小操作數。標準編輯距離（Levenshtein Distance）問題，O(nm) DP 解決。

DP 狀態定義

dp[i][j]：將 X 前 i 字符轉化為 Y 前 j 字符的最小操作數。

初始化

if (X[i-1] == Y[j-1]) cost = 0; else cost = 1;
dp[i][j] = min(
    dp[i-1][j-1] + cost,  // 替換/匹配
    dp[i-1][j] + 1,       // 刪除 X[i-1]
    dp[i][j-1] + 1        // 插入 Y[j-1]
);

完整代碼

空間優化（滾動數組）
只需保留前一行：

輸出具體操作序列
從 dp[n][m] 回溯：
0 && dp[i][j]==dp[i-1][j]+1) {
        printPath(i-1,j);
        printf("Delete %c\n",X[i-1]);
    } else {
        printPath(i,j-1);
        printf("Insert %c\n",Y[j-1]);
    }
}


複雜度

時間：O(nm)，n,m ≤ 1000 → 10⁶ 操作，極快。
空間：O(nm) 或 O(min(n,m))。


總結
編輯距離是動態規劃教科書級例題。掌握「三操作轉移、初始化邊界、回溯輸出路徑」完整流程，可解決所有字符串相似度匹配問題。POJ 3356 數據範圍適中，基礎 DP 即可 AC。