题解：SP6219 EDIST - Edit distance
FireheartQwQ
·
·
题解
双倍经验好诶！
从题面上来看，从一个字符串中删除一个字母，向一个字符串中插入一个字母，将一个字符串中的一个字母替换为另一个字母，这就是动态规划的编辑距离原题！
来让我们回顾一下编辑距离的做法：
几个行动的动态转移方程如下：
不动：无需改变，$dp_{i,j}=dp_{i-1,j-1}$。
删除：将 $A$ 串删除一个字符，$i$ 要减一，多一步操作：$dp_{i,j}=dp_{i-1,j}+1$。
添加：将 $A$ 串添加一个字符，相当于将 $B$ 串删除一个字符，$j$ 要减一，多一步操作：$dp_{i,j}=dp_{i,j-1}+1$。
改变：相当于承接将上一步状态再改变，多一步操作：$dp_{i,j}=dp_{i-1,j-1}+1$。
整合一下：
如果 $a_i=b_i$：$dp_{i,j}=dp_{i-1,j-1}$。
否则：$dp_{i,j}=\min(dp_{i-1,j-1}+1,dp_{i-1,j}+1,dp_{i,j-1}+1)$。
代码：
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char a[2005],b[2005];
int x,y,dp[2005][2005],k;
int main() {
cin>>a>>b;
x=strlen(a),y=strlen(b);
for(int i=x;i>=1;i--) a[i]=a[i-1];
for(int i=y;i>=1;i--) b[i]=b[i-1];
for(int i=0;i<=x;i++) dp[i][0]=i;
for(int i=0;i<=y;i++) dp[0][i]=i;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
k=1;
if(a[i]==b[j]) k=0;
dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+k);
}
}
cout<<dp[x][y];
return 0;
}
```