#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#define FORa(i,s,e) for(int i=s;i<=e;i++)
#define FORs(i,s,e) for(int i=s;i>=e;i--)

using namespace std;

const int N=2000;
string sta,stb;
int m,n,f[N+1][N+1];//f[i][j]字符串sta(sta[0]-sta[i-1])转化到字符串stb(stb[0]-stb[j-1])的最短编辑距离
inline int min(int a,int b){return a<b?a:b;}
int main()
{
cin>>sta>>stb;
n=sta.size(),m=stb.size();
memset(f,127/3,sizeof(f));
FORa(i,1,n) f[i][0]=i;
FORa(i,1,m) f[0][i]=i;
f[0][0]=0;//注意边界与初值，当两字符串中存在空串处理
FORa(i,1,n)
FORa(j,1,m)
if(sta[i-1]==stb[j-1]) f[i][j]=f[i-1][j-1];//当当前字符相同 ，答案等于之前每个减一位的答案
else f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
//f[i-1][j-1]表示把sta[i-1]改成stb[j-1] f[i-1][j]表示把字符串sta中的sta[i]删除 f[i][j-1]表示字符串sta后插入stb[j]
printf("%d",f[n][m]);
return 0;
}

wy