#include <bits/stdc++.h>
using namespace std;
char a[2010],b[2010];
int dp[2010][2010];
int main()
{
	cin >>a+1>>b+1;
	int c=strlen(a+1),d=strlen(b+1);
	for(int i = 1;i<= c;i++)
	{
		for(int j = 1;j <= d;j++)
		{
			if(i==0)
			{
				dp[i][j]=j;
			}
			else if(j==0)
			{
				dp[i][j]=i;
			}
			else
			{
				dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+(a[i]!=b[i]));
			}
		}
	}
	cout <<dp[c][d];
	return 0;
}

https://www.luogu.com.cn/problem/P2758