1. 题目

传送门= ̄ω ̄=

2. 题解

我记得我一年前在考试中推出了递推式。。。
可是我现在居然不会做了/(ㄒoㄒ)/~~
为什么我的智力可以下降的如此迅速。。。

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

设$f(i,j)$为A的前i个字符到B的前j个字符的编辑距离。
递推式:
$f(i,j)=max(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$

代码: