edit distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character

c) Replace a character

      嗯~~这道题用dp来做~~

#include<iostream>
#include<string>
#include<cstring>	
int dp[1000][1000];
int minn(int a,int b,int c)
{
	if(a<=b&&a<=c)
	{
		return a;
	}
	else if(b<=a&&b<=c)
	{
		return b;
	}
	else if(c<=a&&c<=b)
	{
		return c;
	}
}
int main() 
{
	std::ios::sync_with_stdio(false);
	std::string yuan;
	std::string md;
	std::cin>>yuan>>md;
	int leny=yuan.length();
	int lenm=md.length();
	for(int s=0;s<=leny;s++)
	{
		dp[s][0]=s;
	}
	for(int s=0;s<=lenm;s++)
	{
		dp[0][s]=s;
	}
	for(int s=1;s<=leny;s++)
	{
		for(int x=1;x<=lenm;x++)
		{
			int spot=1;
			if(yuan[s-1]==md[x-1])
			{
				spot=0;
			}
			dp[s][x]=minn(dp[s-1][x]+1,dp[s][x-1]+1,dp[s-1][x-1]+spot);
		}
	}
	for(int s=0;s<=leny;s++)
	{
		for(int x=0;x<=lenm;x++)
		{
			std::cout<<dp[s][x];
		}
		std::cout<<std::endl;
	}
	std::cout<<dp[leny][lenm]<<std::endl;
	return 0;
}