计算字符串的相似度

核心提示：下面再来详细说说什么是重叠子问题，适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要“很小”，计算字符串的相似度(3)，也就是用来解原问题的递归算法可以反复地解同样的子问题，而不是总在产生新的子问题，把解保存在一个需要时就可以查看的表中，而每次查表的时间为常数，典型地，不同的子问

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

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

DP Algorithm

　1 /*
　2　 * A loop method using dynamic programming.
　3　 * Calculate from bottom to top.
　4　 */
　5 int calculateStringDistance(string strA, string strB)
　6 {
　7　　　　 int lenA = (int)strA.length();
　8　　　　 int lenB = (int)strB.length();
　9　　　　 int c[lenA+1][lenB+1]; // Record the distance of all begin points of each string
10
11　　　　 // i: begin point of strA
12　　　　 // j: begin point of strB
13　　　　 for(int i = 0; i < lenA; i++) c[i][lenB] = lenA - i;
14　　　　 for(int j = 0; j < lenB; j++) c[lenA][j] = lenB - j;
15　　　　 c[lenA][lenB] = 0;
16
17　　　　 for(int i = lenA-1; i >= 0; i--)
18　　　　　　　　 for(int j = lenB-1; j >= 0; j--)
19　　　　　　　　 {
20　　　　　　　　　　　　 if(strB[j] == strA[i])
21　　　　　　　　　　　　　　　　 c[i][j] = c[i+1][j+1];
22　　　　　　　　　　　　 else
23　　　　　　　　　　　　　　　　 c[i][j] = minValue(c[i][j+1], c[i+1][j], c[i+1][j+1]) + 1;
24　　　　　　　　 }
25
26　　　　 return c[0][0];
27 }