问题：编辑距离，是指将一个字符串变为另一个字符串，仅可以3种操作：修改一个字符，删除一个字符，插入一个字符。the变成that：删除e，插入a，插入t。20’
实现编辑距离算法。
解算：利用动态规划的思想，将问题分解为各个子问题，解决子问题从而得到最终的答案。
思路如下：
字符串S1和S2
S1和S2的编辑距离的子问题为S1的任意子字符串到S2的任意子字符串的编辑距离。。。。。。
从而，S1到S2的编辑距离可以存储(len1+1)*(len2+1)大小的矩阵中
当S1、S2都为空时，编辑距离（editDistance）为0；
当S1、S2中有一个为空时，编辑距离明显为不为空的字符串的长度；
当S1、S2都不为空时，editDistance(S1,S2)可以看做是在其前一步的决策后增加了一步操作，其前一步的编辑距离主要来自三个方向：（S1[1:len1-1]、S2）、(S1[len1]、S2[1:len2-1])、（S1[1:len1-1]、S2[1:len2-1]）
其中（S1[1:len1-1]、S2[1:len2-1]）操作比较特殊，如果比较的当前值相等，就不需要操作了，不相等就操作+1。因此editDistance(S1,S2) = min(1,2,3)中情况中最小值。
具体代码如下：参考：http://blog.csdn.net/yysdsyl/article/details/4249245
int min(int a,int b,int c)
{
int t = a<b?a:b;
return t<c?t:c;
} void editDistance(char s1[],char s2[])
{
int len1 = strlen(s1);
int len2 = strlen(s2); int **d = new int*[len1+];
for(int k = ;k<=len1;k++)
d[k] = new int[len2+];
int i,j;
for(i = ;i<=len1;i++)
d[i][] = i;
for(j = ;j<=len2;j++)
d[][j] = j;
for(i = ;i<=len1;i++)
{
for(j = ;j<=len2;j++)
{
int cost = s1[i-] == s2[j-]?:;
int deletion = d[i-][j] + ;
int insertion = d[i][j-] +;
int substitution = d[i-][j-] + cost;
d[i][j] = min(deletion,insertion,substitution);
printf("%3d",d[i][j]);
}
printf("\n");
}
printf("%d\n",d[len1][len2]);
for(int k = ;k<=len1;k++)
delete[] d[k];
delete[] d;
} int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv); char s1[] = "fxpium";
char s2[] = "xwrs";
editDistance(s1,s2); return a.exec();
}