7-8 编辑距离问题 （30 分)
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。

输入格式:
第一行是字符串A，文件的第二行是字符串B。

提示：字符串长度不超过2000个字符。

输出格式:
输出编辑距离d(A,B)

输入样例:
在这里给出一组输入。例如：

fxpimu
xwrs
输出样例:
在这里给出相应的输出。例如：

5

分析：
这道题经分析有三种操作，
1，当字符串有一个不匹配的时候直接删除
2，当少一个字符的时候插入一个字符，但这个可以转化为操作一，所以这个并没有什么卵用。不用考虑。
3，将一个字符该改为另一个字符，用于有两个字符不同，如果我们删除需要两个操纵，但我们使用修改为另一个字符的话，我们的操作只需要一次就好。

那么我们试着用一下动态规划的思想，将原问题划分成与原问题相同的子问题，看看可不可以递推。

加入我们已经直到了a[0]-a[i-1] 这个串和 b[0]-b[j-1] 这个串的距离为x，
那么a[0]-a[i] 和 b[0]-b[j] 这个原问题的解是什么呢？

可知，如果a[i]==b[j]那么dp[i][j] 的答案就是 dp[i-1][j-1]
如果a[i]!=b[j] 那么dp[i][j] 的答案将会是，
删除a[i]: 1+dp[i-1][j], 删除b[j]: 1+dp[i][j] , 修改a[i] 使 a[i]==b[j]: 1+dp[i-1][j-1]
这三个操作中答案最小的那个。

可知可以使用动态规划，
在实际书写代码的时候注意dp数组的初始化。
详见代码：

#include<bits/stdc++.h> 
using namespace std;

const int maxn=2001;

string a,b;

int dp[maxn][maxn];

int main()
{
	//freopen("in.txt","r",stdin);
	memset(dp,0,sizeof(dp));
	cin>>a>>b;
	a=" "+a;
	b=" "+b;
	
	for(int i=0;i!=a.size();i++)
	{
		dp[i][0]=i;
	}
	
	for(int j=0;j!=b.size();j++)
	{
		dp[0][j]=j;
	}
	
	for(int i=1;i!=a.size();i++)
	{
		for(int j=1;j!=b.size();j++)
		{
			if(a[i]==b[j])
			{
				dp[i][j]=dp[i-1][j-1];
			}
			else
			{
				int t=min(dp[i-1][j],dp[i][j-1])+1;
				t = min(t,dp[i-1][j-1]+1);
				dp[i][j]=t;
			}
		}
	}
	
//	for(int i=0;i!=a.size();i++)
//	{
//		for(int j=0;j!=b.size();j++)
//		{
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	
	cout<<dp[a.size()-1][b.size()-1]<<endl;
	return 0;
}