设 A 和 B 是 2 个字符串。要用最少的字符操作将字符串 A
转换为字符串 B。这里所说的
字符操作包括
(1)删除一个字符；
(2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串
A 到 B 的编辑距离，记为
d(A,B)。试设计一个有效算法，对任给的
2 个字符串 A 和 B，计算出它们的编辑距离 d(A,B)。
«编程任务：
对于给定的字符串 A 和字符串 B，编程计算其编辑距离 d(A,B)。
#include<bits/stdc++.h>
using namespace std;
string n,m;
int dp[5005][5005];
int main(){
cin>>n>>m;
int lenl,len2;
lenl=n.size();
len2=m.size();
dp[0][0]=0;
for(int i=0;i<=lenl;i++){
dp[i][0]=i;
}
for(int j=0;j<=len2;j++){
dp[0][j]=j;
}
for(int i=1;i<=lenl;i++){
for(int j=1;j<=len2;j++){
if(n[i-1]==m[j-1]){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
}
}
cout<<dp[lenl][len2];
}