f507 - 1207 - AGTC

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算將字串 x 轉換為字串 y 所需的最少操作次數。允許的操作包括插入、刪除和替換。每次操作的成本為 1。

解題思路

本題可以使用動態規劃 (Dynamic Programming) 解決，這是一個經典的編輯距離 (Edit Distance) 問題。定義 dp[i][j] 為將字串 x 的前 i 個字元轉換為字串 y 的前 j 個字元所需的最少操作次數。

狀態轉移方程如下：

• 如果 x[i] == y[j]，則 dp[i][j] = dp[i-1][j-1] (無需操作)
• 如果 x[i] != y[j]，則 dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1) (分別對應刪除、插入和替換操作)

初始化：

• dp[i][0] = i (將 x 的前 i 個字元轉換為空字串需要刪除 i 個字元)
• dp[0][j] = j (將空字串轉換為 y 的前 j 個字元需要插入 j 個字元)

最終結果為 dp[xl][yl]，其中 xl 和 yl 分別為字串 x 和 y 的長度。

複雜度分析

• 時間複雜度: O(xl * yl)，其中 xl 和 yl 分別是字串 x 和 y 的長度。因為需要遍歷一個 xl x yl 的二維陣列。
• 空間複雜度: O(xl * yl)，因為需要一個 xl x yl 的二維陣列來儲存 dp 值。

程式碼

#include <iostream>
using namespace std;
int dp[2005][2005],xl,yl;
string x,y;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> xl >> x >> yl >> y){
		x=' '+x;
		y=' '+y;
		for(int i=0;i<=xl;++i){
			dp[i][0]=i;
		}
		for(int j=0;j<=yl;++j){
			dp[0][j]=j;
		} 
		for(int i=1;i<=xl;++i){
			for(int j=1;j<=yl;++j){
				dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+!(x[i]==y[j])));
			}
		}
		cout << dp[xl][yl] << "\n";
	}
}