【题目描述】

【思路】

设 $dp[i][j]$ 表示把字符串a的前i个字符变成字符串b的前j个字符的编辑距离，有转移方程

dp[i+1][j+1]={dp[i][j]+(a[i]==b[j] ? 0: 1)dp[i][j+1]+1dp[i+1][j]+1dp[i+1][j+1]=\begin{cases} dp[i][j]+(a[i]==b[j] \ ? \ 0: \ 1) \\ dp[i][j+1]+1 \\ dp[i+1][j]+1 \end{cases}dp[i+1][j+1]=⎩⎪⎨⎪⎧​dp[i][j]+(a[i]==b[j] ? 0: 1)dp[i][j+1]+1dp[i+1][j]+1​

第一项表示在将a的前i项变成b的前j项的基础上再添加一个字符，如果字符不同则修改

第二项表示将a的前i+1项删掉最后1项，再将剩下的i项变为b的前j+1项

第三项表示将a的前i+1项变成b的前j项，再添加一个字符变为b的前j+1项

#include
    
     using namespace std;const int inf=2e9;const int maxn=1005;int lens,lent;char s[maxn],t[maxn];int dp[maxn][maxn];int main(){	scanf("%s%s",s,t);	lens=strlen(s);	lent=strlen(t);	for(int i=0;i<=lens;++i) dp[i][0]=i;	for(int j=0;j<=lent;++j) dp[0][j]=j;	for(int i=0;i