#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int f[N][N];
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	s1=" "+s1;
	s2=" "+s2;
	int n=s1.size(),m=s2.size();
	for(int i=1;i<=n;i++)
	{
		f[i][0]=i;	
	}
	for(int i=1;i<=m;i++)
	{
		f[0][i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
	    {
			f[i][j]=min(f[i-1][j],f[i][j-1])+1;
			if(s1[i]==s2[j])
			{
				f[i][j]=min(f[i][j],f[i-1][j-1]);
			}
			else
			{
				f[i][j]=min(f[i][j],f[i-1][j-1]+1);
			}
		}
	} 
	cout<<f[n][m];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int f[N][N];//f[i][j]±íʾµÚÒ»¸ö×Ö·û´®µÄÇ°i¸ö×Ö·û£¬µÚ¶þ¸ö×Ö·û´®µÄÇ°j¸ö×Ö·û£¬±ä³ÉÏàͬ´®×îÉÙÐèÒªµÄ²Ù×÷´ÎÊý 
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	s1=" "+s1;
	s2=" "+s2;
	int n=s1.size(),m=s2.size();
	for(int i=1;i<=n;i++) f[i][0]=i;
	for(int i=1;i<=m;i++) f[0][i]=i;
	for(int i=1;i<=n;i++)
    {
		for(int j=1;j<=m;j++)
        {
			f[i][j]=min(f[i-1][j],f[i][j-1])+1;
			if(s1[i]==s2[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
			else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
		}
	} 
   	cout<<f[n][m];
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int f[N][N]; //f[i][j]表示第一个串的前i个字符和第二个串的前j个字符变成相同的最少操作次数 
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	int n=s1.size(),m=s2.size();
	s1=" "+s1; //方便字符串下标从1开始 
	s2=" "+s2;
	for(int i=1;i<=n;i++) f[i][0]=i; //删除第一个串的所有字符 
	for(int i=1;i<=m;i++) f[0][i]=i; //删除第二个串的所有字符 
	for(int i=1;i<=n;i++)
    {
		for(int j=1;j<=m;j++)
        {
			f[i][j]=min(f[i-1][j],f[i][j-1])+1; //删除第一个串的第i个字符或者是第二个串的第j个字符 
			if(s1[i]==s2[j]) f[i][j]=min(f[i][j],f[i-1][j-1]); //相同可以直接从f[i-1][j-1]过来 
			else f[i][j]=min(f[i][j],f[i-1][j-1]+1); //将s2[j]变成s1[i] 
		}
	} 
   	cout<<f[n][m];
    return 0;
}

#include<bits/stdc++.h> using namespace std; const int N=3010; int f[N][N];//f[i][j]±íʾµÚÒ»¸ö×Ö·û´®µÄÇ°i¸ö×Ö·û£¬µÚ¶þ¸ö×Ö·û´®µÄÇ°j¸ö×Ö·û£¬±ä³ÉÏàͬ´®×îÉÙÐèÒªµÄ²Ù×÷´ÎÊý int main() { string s1,s2; cin>>s1>>s2; s1=" "+s1; s2=" "+s2; int n=s1.size(),m=s2.size(); for(int i=1;i<=n;i++) f[i][0]=i; for(int i=1;i<=m;i++) f[0][i]=i; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f[i][j]=min(f[i-1][j],f[i][j-1])+1; if(s1[i]==s2[j]) f[i][j]=min(f[i][j],f[i-1][j-1]); else f[i][j]=min(f[i][j],f[i-1][j-1]+1); } } cout<<f[n][m]; return 0; }