SDUT 1225 編輯距離：經典字符串 DP

問題描述

允許刪除、插入、替換三種操作，求將字符串 A 轉換為 B 的最小操作數（編輯距離）。長度 ≤ 1024。

DP 定義

dp[i][j] 表示 A 前 i 字符變為 B 前 j 字符的最小編輯距離。

轉移方程

dp[i][j] = min(
    dp[i-1][j] + 1,        // 刪除 A[i]
    dp[i][j-1] + 1,        // 插入 B[j]
    dp[i-1][j-1] + (A[i]==B[j] ? 0 : 1)  // 匹配或替換
)

邊界

dp[0][j] = j（全插入），dp[i][0] = i（全刪除）。

代碼

#include <cstdio> #include <cstring>
#define MAXN 1025
int dp[MAXN][MAXN];
char a[MAXN], b[MAXN];
int main() {
    while (~scanf("%s%s", a, b)) {
        int la = strlen(a), lb = strlen(b);
        for (int i = 0; i <= lb; i++) dp[0][i] = i;
        for (int i = 0; i <= la; i++) dp[i][0] = i;
        for (int i = 1; i <= la; i++)
            for (int j = 1; j <= lb; j++)
                dp[i][j] = std::min({dp[i-1][j]+1, dp[i][j-1]+1,
                    dp[i-1][j-1] + (a[i-1]==b[j-1] ? 0 : 1)});
        printf("%d\n", dp[la][lb]);
    }
    return 0;
}

優化提示

空間可優化至 O(min(n,m))，僅保留兩行。但 1024² ≈ 1M int，內存 4MB，完全可接受。