题目描述：

许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。
我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：
　　1.修改一个字符（如把“a”替换为“b”）;
　　2.增加一个字符（如把“abdd”变为“aebdd”）;
　　3.删除一个字符（如把“travelling”变为“traveling”）;
比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。
上面的两种方案，都仅需要一次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。
也就是说，“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5。
给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？

分析与解法：　

　　我们还是就住集中考虑如何才能把这个问题转化成规模较小的同样的子问题。
如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是相同的，
只要计算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距离就可以了。
但是如果两个串的第一个字符不相同，那么可以进行如下的操作（lenA和lenB分别是A串和B串的长度）。
　1.删除A串的第一个字符，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
　2.删除B串的第一个字符，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
　3.修改A串的第一个字符为B串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
  4.修改B串的第一个字符为A串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
  5.增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
  6.增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。

在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。
所以，可以将上面的6个操作合并为：
　　1.一步操作之后，再将A[2,...,lenA]和B[1,...,lenB]变成相字符串。
　　2.一步操作之后，再将A[2,...,lenA]和B[2,...,lenB]变成相字符串。
　　3.一步操作之后，再将A[1,...,lenA]和B[2,...,lenB]变成相字符串。
　　这样，很快就可以完成一个递归程序。

int calculateStringDistance(string strA, int pABegin, int pAEnd, string strB, int pBBegin, int pBEnd)
 {
　　　　 if(pABegin>pAEnd)
　　　　 {
　　　　　　　　 if(pBBegin>pBEnd)
　　　　　　　　　　　return 0;
　　　　　　　　 else
　　　　　　　　　　　return pBEnd-pBBegin+1;
　　　　 }
　　　　 if(pBBegin>pBEnd)
　　　　 {
　　　　　　　　 if(pABegin>pAEnd)
　　　　　　　　　　　return 0;
　　　　　　　　 else
　　　　　　　　　　　return pAEnd-pABegin1;
　　　　 }
　　　　 if(strA[pABegin]==strB[pBBegin])
　　　　 {
　　　　　　　　 return calculateStringDistance(strA,pABegin+1,pAEnd,strB,pBBegin+1, pBEnd);
　　　　 }
　　　　 else
　　　　 {
　　　　　　　int t1 = calculateStringDistance(strA, pABegin, pAEnd, strB, pBBegin+1, pBEnd);
　　　　　　　int t2 = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin, pBEnd);
　　　　　　　int t3 = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin+1, pBEnd);
　　　　　　　return minValue(t1, t2, t3) + 1;
　　　　 }
 }

扩展问题; 

上面的递归程序，有什么地方需要改进呢？问题在于：在递归的过程中，有些数据被重复计算了。 
解法：
可以采用DP；或者备忘录形式； 
DP： 
动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。

 int calculateStringDistance(string strA, string strB)
 {
　　　　 int lenA=(int)strA.length();
　　　　 int lenB=(int)strB.length();
　　　　 int c[lenA+1][lenB+1]; 
        
        //初始化边界 长度 
　　　　 for(int i=0;i<lenA;i++) //距离为对方长度 
			c[i][lenB]=lenA-i;
　　　　 for(int j=0;j<lenB;j++) 
			c[lenA][j]=lenB-j;
			
　　　　 c[lenA][lenB]=0;
　　　　 for(int i=lenA-1; i>=0; i--)
　　　　　　　　 for(int j=lenB-1; j>=0; j--)
　　　　　　　　 {
　　　　　　　　　　　if(strB[j]==strA[i])
　　　　　　　　　　　　　　　c[i][j]=c[i+1][j+1];
　　　　　　　　　　　　 else
　　　　　　　　　　　　　　　c[i][j]=min(c[i][j+1],c[i+1][j],c[i+1][j+1]) + 1;
　　　　　　　　 }
　　　　 return c[0][0];
 }