计算字符串的相似度

核心提示：原文算法代码1 int calculateStringDistance(string strA, int pABegin, int pAEnd, string strB, int pBBegin, int pBEnd)2 {3 if(pABegin > pAEnd)4 {5 if(pBBegin > pBE

原文算法代码

　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步的计算中记录一些附加信息，使构造一个最优解变得容易。

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