程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SDUT 1225-編輯距離(串型dp)

SDUT 1225-編輯距離(串型dp)

編輯：C++入門知識

SDUT 1225-編輯距離(串型dp)

編輯距離

Time Limit: 1000ms Memory limit: 65536K 有疑問？點這裡^_^

題目描述

假設字符串的基本操作僅為：刪除一個字符、插入一個字符和將一個字符修改成另一個字符這三種操作。
我們把進行了一次上述三種操作的任意一種操作稱為進行了一步字符基本操作。
下面我們定義兩個字符串的編輯距離：對於兩個字符串a和b，通過上述的基本操作，我們可以把a變成b或b變成a，那麼字符串a變成字符串b需要的最少基本字符操作步數稱為字符串a和字符串b的編輯距離。
例如：a="ABC",b="CBCD",則a與b的編輯距離為2。
你的任務就是：編一個快速的程序來計算任意兩個字符串的編輯距離。

輸入

輸入包含多組測試數據。每組測試數據一行，為字符串A和字符串B。
字符串的長度不大於1024，且全為字母。

輸出

編輯距離。

示例輸入

ABC CBCD

示例輸出

一開始想爆搜，一看范圍傻了。。。串模型DP。

設dp[i][j]代表原始串從1到i位置上與目標串從1到j位置上的最短編輯距離，

dp[i][j]=min(dp[i][j-1]+1(刪除a[i]),dp[i-1][j]+1(增加b[j]),a[i]==b[j]?dp[i-1][j-1]:dp[i-1][j-1]+1);

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[1025][1025];
char a[1025],b[1025];
int My_min(int x,int y,int z)
{
	return min(min(x,y),z);
}
int main()
{
	while(~scanf("%s%s",a,b))
	{
		int lena=strlen(a),lenb=strlen(b);
		for(int i=0;i<=lenb;i++)
			dp[0][i]=i;
		for(int i=0;i<=lena;i++)
			dp[i][0]=i;
		for(int i=1;i<=lena;i++)
			for(int j=1;j<=lenb;j++)
			dp[i][j]=My_min(dp[i-1][j]+1,dp[i][j-1]+1,a[i-1]==b[j-1]?dp[i-1][j-1]:dp[i-1][j-1]+1);
		printf("%d\n",dp[lena][lenb]);
	}
	return 0;
}