1. 题目

传送门＝￣ω￣＝

2. 题解

我记得我一年前在考试中推出了递推式。。。
可是我现在居然不会做了／（ㄒｏㄒ）／～～
为什么我的智力可以下降的如此迅速。。。

首先，不难发现 a 到 b 的编辑距离=b 到 a 的编辑距离

设 $f(i,j)$为 A 的前 i 个字符到 B 的前 j 个字符的编辑距离。
递推式：
$f(i,j)=min(f(i,j-1),f(i-1,j),f(i-1,j-1))+1 (A[i]!=B[j])$
$f(i,j)=f(i-1,j-1) (A[i]==B[j])$
$f(i,0)=f(0,i)=i$

代码：

#include <bits/stdc++.h>
using namespace std;
char s1[2005],s2[2005];
int l1,l2,f[2005][2005];
int main()
{
    scanf("%s",s1+1),scanf("%s",s2+1),l1=strlen(s1+1),l2=strlen(s2+1);
    for(int i=1;i<2005;i++)f[0][i]=f[i][0]=i;
    for(int i=1;i<=l1;i++)
        for(int j=1;j<=l2;j++)
            if(s1[i]==s2[j])f[i][j]=f[i-1][j-1];
            else f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
    printf("%d\n",f[l1][l2]);
    return 0;
}