最短编辑距离(详细分析)
算法思想: dp[i][j]表示a1~ai变为b1~bj所要花费的最小编辑次数
dp[i][j]=min{dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1/0}
集合划分:
第一项:a1,a2,a3...ai-1,[ai]
b1,b2,b3...bj-1,bj
a1~ai-1已经和b1~bj匹配,花费的次数为dp[i-1][j]
现在只要删除ai即可将两个字符串匹配,所以dp[i][j]=dp[i-1][j]+1(1次删除操作)
或者在bj后面加上一个ai也可以实现上下两个字符串匹配
a1,a2,a3...ai-1,ai
b1,b2,b3...bj-1,bj,[ai] dp[i][j]=dp[i-1][j]+1(1次删增加操作)
但是题目规定了b字符串不能动!所以第二种方案不可行
综上, dp[i][j]=dp[i-1][j]+1(1次删除操作);
第二项:a1,a2,a3...ai-1,ai
b1,b2,b3...bj-1,[bj]
a1~ai和b1~bj-1已经实现匹配,花费的次数为dp[i][j-1]
分析方法同第一项,dp[i][j]=dp[i][j-1](增加bj到a中为一次增加操作)
第三项: a1,a2,a3,...ai-1,[ai]
b1,b2,b3,...bj-1,[bj]
最后一种情况是a1~ai-1与b1~bj-1匹配,花费的次数为dp[i-1][j-1]
实现a1~ai与b1~bj匹配的方法分两种情况:
A. ai=bj的时候,那皆大欢喜,不用动就实现了匹配
dp[i][j]=dp[i-1][j-1]+0(不用动)
B. ai≠bj的时候,
由于b不能动只能动a,所以只能有两种方法
(倘若bj可以动,还会多出来两种方法:ai前面插bj,bj后面加ai
或bj前面插ai,ai后面加bj)
1.删除ai再添加bj —— 两次操作
2.直接修改ai为bj —— 一次"改"操作
这肯定选后面一种方法(次数最少)
此外,一定设置初值,否则都默认为0,不符合题意
dp[i][0]=i(长度为i的a变为长度为0的b最少要对a经过i次删除才行)
dp[0][j]=j(长度为0的a变为长度为j的b最少要对a经过j次添加才行)
C++代码
#include<iostream>
using namespace std;
const int M=1010;
int dp[M][M];
int main(){
int n,m; char a[M],b[M];
cin>>n>>a+1>>m>>b+1;
for(int i=1;i<=n;i++) dp[i][0]=i;
for(int j=1;j<=m;j++) dp[0][j]=j;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
}
cout<<dp[n][m]<<endl;
return 0;
}