计算两个字符串的相似度（递归和DP）

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]变成相字符串。

这样，很快就可以完成一个递归程序。 

 1 int calculateStringDistance(string strA, int pABegin, int pAEnd, string strB, int pBBegin, int pBEnd)
 2 {
 3     if(pABegin > pAEnd)
 4     {
 5         if(pBBegin > pBEnd)
 6             return 0;
 7         else
 8             return pBEnd - pBBegin + 1;
 9     }
10 
11     if(pBBegin > pBEnd)
12     {
13         if(pABegin > pAEnd)
14             return 0;
15         else
16             return pAEnd - pABegin + 1;
17     }
18 
19     if(strA[pABegin] == strB[pBBegin])
20     {
21         return calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin+1, pBEnd);
22     }
23     else
24     {
25         int t1 = calculateStringDistance(strA, pABegin, pAEnd, strB, pBBegin+1, pBEnd);
26         int t2 = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin, pBEnd);
27         int t3 = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin+1, pBEnd);
28         return minValue(t1, t2, t3) + 1;
29     }
30 }

上面的递归程序，有什么地方需要改进呢？问题在于：在递归的过程中，有些数据被重复计算了。

我们知道适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。另外，还有一种方法称为备忘录（memoization），可以充分利用重叠子问题的性质。

下面简述一下动态规划的基本思想。和分治法一样，动态规划是通过组合子问题的解而解决整个问题的。我们知道，分治算法是指将问题划分 成一睦独立的子问题，递归 地求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划适用于子问题不是独立 的情况，也就是各子问题包含公共的子子问题。在这种情况 下，若用分治法则会做许多不必要的工作，即重复地求解公共的子子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

动态规划通常应用于最优化问题。此类问题可能有很多种可行解，每个解有一个值，而我们希望找出一个具有最优（最大或最小）值的解。称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优值的解。

动态规划算法的设计可以分为如下4个步骤：

1）描述最优解的结构。
2）递归定义最优解的值。
3）按自底向上的方式计算最优解的值。
4）由计算出的结果构造一个最优解。

第1~3步构成问题的动态规划解的基础。第4步在只要求计算最优解的值时可以略去。如果的确做了第4步，则有时要在第3步的计算中记录一些附加信息，使构造一个最优解变得容易。

该问题明显完全符合动态规划的两个要素，即最优子结构和重叠子问题特性。该问题的最优指的是两个字符串的最短距离，子问题的重叠性可以从原书中的那个递归算法中看出。

下面再来详细说说什么是重叠子问题。适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要“很小”，也就是用来解原问题的递归算法可以反复地解同样的子问题，而不是总在产生新的子问题。典型地，不同的子问题数是输入规模的一个多项式。当一个递归算法不断地调用同一问题时，我们说该最优问题包含重叠子问题。相反地，适合用分治法解决的问题只往往在递归的每一步都产生全新的问题。动态规划算法总是充分利用重叠子问题，即通过每个子问题只解一次，把解保存在一个需要时就可以查看的表中，而每次查表的时间为常数。

根据以上的分析，我写了如下的动态规划算法：

原文出处：http://www.cnblogs.com/suyang/archive/2009/08/03/1488201.html