计算字符串的相似度

核心提示：最后再说说“备忘录”法，其实它算是动态规划的一种变形，计算字符串的相似度(4)，它既具有通常的动态规划方法的效率，又采用了一种自顶向下的策略，如果子问题空间中的某些子问题根本没有必要求解，做备忘录方法有着只解那些肯定要求解的子问题的优点，其思想就是备忘原问题的自然但低效的递归算法，像在通常的动态

最后再说说“备忘录”法。其实它算是动态规划的一种变形，它既具有通常的动态规划方法的效率，又采用了一种自顶向下的策略。其思想就是备忘原问题的自然但低效的递归算法。像在通常的动态规划中一样，维护一个记录了子问题解的表，但有关填表动作的控制结构更像递归算法。

加了备忘的递归算法为每一个子问题的解在表中记录一个表项。开始时，每个表项最初都包含一个特殊的值，以表示该表项有待填入。当在递归算法的执行中第一次遇到一个子问题时，就计算它的解并填入表中。以后每次遇到该子问题时，只要查看并返回先前填入的值即可。

下面是原文递归算法的做备忘录版本，并通过布尔变量memoize来控制是否使用备忘录，以及布尔变量debug来控制是否打印调用过程。有兴趣的读都可以通过这两个布尔变量的控制来对比一下备忘录版本与非备忘录版本的复杂度。

备忘录版

　 1 #include <iostream>
　 2 #define M 100
　 3
　 4 using namespace std;
　 5
　 6 const bool debug = false; // Whether to print debug info
　 7 const bool memoize = true; // Whether to use memoization
　 8 unsigned int cnt = 0; // Line number for the debug info
　 9
　10 int memoizedDistance[M][M]; // Matrix for memoiztion
　11
　12 int minValue(int a, int b, int c)
　13 {
　14　　　　 if(a < b && a < c) return a;
　15　　　　 else if(b < a && b < c) return b;
　16　　　　 else return c;
　17 }
　18
　19 /*
　20　 * A recursive method which can be decorated by memoization.
　21　 * Calculate from top to bottom.
　22　 */
　23 int calculateStringDistance(string strA, int pABegin, int pAEnd, string strB, int pBBegin, int pBEnd)
　24 {
　25　　　　 if(memoize && memoizedDistance[pABegin][pBBegin] >= 0)
　26　　　　　　　　 return memoizedDistance[pABegin][pBBegin];
　27
　28　　　　 if(pABegin > pAEnd)
　29　　　　 {
　30　　　　　　　　 if(pBBegin > pBEnd)
　31　　　　　　　　 {
　32　　　　　　　　　　　　 if(memoize)
　33　　　　　　　　　　　　　　　　 memoizedDistance[pABegin][pBBegin] = 0;
　34　　　　　　　　　　　　 if(debug)
　35　　　　　　　　　　　　　　　　 cout << cnt++ << ": m(" << pABegin << "," << pBBegin << ")=0" << endl;
　36　　　　　　　　　　　　 return 0;
　37　　　　　　　　 }
　38　　　　　　　　 else
　39　　　　　　　　 {
　40　　　　　　　　　　　　 int temp = pBEnd - pBBegin + 1;
　41　　　　　　　　　　　　 if(memoize)
　42　　　　　　　　　　　　　　　　 memoizedDistance[pABegin][pBBegin] = temp;
　43　　　　　　　　　　　　 if(debug)
　44　　　　　　　　　　　　　　　　 cout << cnt++ << ": m(" << pABegin << "," << pBBegin << ")=" << temp << endl;
　45　　　　　　　　　　　　 return temp;
　46　　　　　　　　 }
　47　　　　 }
　48
　49　　　　 if(pBBegin > pBEnd)
　50　　　　 {
　51　　　　　　　　 if(pABegin > pAEnd)
　52　　　　　　　　 {
　53　　　　　　　　　　　　 if(memoize)
　54　　　　　　　　　　　　　　　　 memoizedDistance[pABegin][pBBegin] = 0;
　55　　　　　　　　　　　　 if(debug)
　56　　　　　　　　　　　　　　　　 cout << cnt++ << ": m(" << pABegin << "," << pBBegin << ")=0" << endl;
　57　　　　　　　　　　　　 return 0;
　58　　　　　　　　 }
　59　　　　　　　　 else
　60　　　　　　　　 {
　61　　　　　　　　　　　　 int temp = pAEnd - pABegin + 1;
　62　　　　　　　　　　　　 if(memoize)
　63　　　　　　　　　　　　　　　　 memoizedDistance[pABegin][pBBegin] = temp;
　64　　　　　　　　　　　　 if(debug)
　65　　　　　　　　　　　　　　　　 cout << cnt++ << ": m(" << pABegin << "," << pBBegin << ")=" << temp << endl;
　66　　　　　　　　　　　　 return temp;
　67　　　　　　　　 }
　68　　　　 }
　69
　70　　　　 if(strA[pABegin] == strB[pBBegin])
　71　　　　 {
　72　　　　　　　　 int temp = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin+1, pBEnd);
　73　　　　　　　　 if(memoize)
　74　　　　　　　　　　　　 memoizedDistance[pABegin][pBBegin] = temp;
　75　　　　　　　　　 if(debug)
　76　　　　　　　　　　　　 cout << cnt++ << ": m(" << pABegin << "," << pBBegin << ")=" << temp << endl;
　77　　　　　　　　 return temp;
　78　　　　 }
　79　　　　 else
　80　　　　 {
　81　　　　　　　　 int t1 = calculateStringDistance(strA, pABegin, pAEnd, strB, pBBegin+1, pBEnd);
　82　　　　　　　　 int t2 = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin, pBEnd);
　83　　　　　　　　 int t3 = calculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin+1, pBEnd);
　84　　　　　　　　 int temp = minValue(t1, t2, t3) + 1;
　85　　　　　　　　 if(memoize)
　86　　　　　　　　　　　　 memoizedDistance[pABegin][pBBegin] = temp;
　87　　　　　　　　 if(debug)
　88　　　　　　　　　　　　 cout << cnt++ << ": m(" << pABegin << "," << pBBegin << ")=" << temp << endl;
　89　　　　　　　　 return temp;
　90　　　　 }
　91 }
　92
　93 int main()
　94 {
　95　　　　 if(memoize)
　96　　　　 {
　97　　　　　　　　 // initialize the matrix : memoizedDistance[][]
　98　　　　　　　　 for(int i = 0; i < M; i++)
　99　　　　　　　　　　　　 for(int j = 0; j < M; j++)
100　　　　　　　　　　　　　　　　 memoizedDistance[i][j] = -1; // -1 means unfilled cell yet
101　　　　 }
102
103　　　　 string strA = "abcdfef";
104　　　　 string strB = "a";
105
106　　　　 cout << endl << "Similarity = "
107　　　　　　　　　　　　 << 1.0 / (1 + calculateStringDistance(strA, 0, (int)strA.length()-1, strB, 0, (int)strB.length()-1))
108　　　　　　　　　　　　 << endl;
109
110　　　　 return 0;
111 }

总结 ： 可以计算出，如果不用动态规划或是做备忘录，最坏情况下复杂度约为：lenA！*lenB！。使用动态规划的复杂度为O(（lenA+1）*（lenB+1）)。递归并做备忘录的方法最坏情况下复杂度为O(（lenA+1）*（lenB+1）)。

在实际应用中，如果所有的子问题都至少要被计算一次，则一个自底向上的动态规划算法通常要比一个自顶向下的做备忘录算法好出一个常数因子，因为前者无需递归的代价，而且维护表格的开销也小些。此外，在有些问题中，还可以用动态规划算法中的表存取模式来进一步减少时间或空间上的需求。或者，如果子问题空间中的某些子问题根本没有必要求解，做备忘录方法有着只解那些肯定要求解的子问题的优点，对于本问题就是这样。