【算法】动态规划算法求（编辑距离）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】动态规划算法求（编辑距离）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

编辑距离：

举例：

代码如下

调试：

核心代码：

画图演示上述代码：

编辑距离：

是一种计算两个自符串之间差异程度的方法，它通过比较两个字符串之间的插入，删除和

替换操作的数量，来确定他们之间的距离。

举例：

现有两个字符串

字符串s1：”CTGA"

字符串s2: "ACGCTA"

求s1和s2的编辑距离

字符串s1得到字符串s2 可以通过如下操作

1. 在字符串s1的C前插入A ----------"ACTGA"

2. 在"ACTGA"字符串中，将T删除 ----------"ACGA"

3. 在"ACGA"字符G和A中插入C ----------"ACGCA"

4. 在"ACGCA"字符C和A中插入T----------"ACGCTA"

综上：字符串s1得到字符串s2至少花了4个步骤，因此字符串是s1与字符串s2之间的

编辑距离为4

代码如下

#include <stdio.h>

#define N 100

char A[N] = "CTGA";
char B[N] = "ACGCTA";
int d[N][N];

int min(int a, int b){
    return a < b ? a : b;
}

int editdistance(char *str1, int len1, char *str2, int len2){
    int i, j, temp;

    for (i = 0; i <= len1; i++) {
        d[i][0] = i;
    }
    for (j = 0; j <= len2; j++) {
        d[0][j] = j;
    }
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                d[i][j] = d[i - 1][j - 1];
            } else {
                temp = min(d[i - 1][j] + 1, d[i][j - 1] + 1);
                d[i][j] = min(temp, d[i - 1][j - 1] + 1);
            }
        }
    }
    return d[len1][len2];
}

int main() {
    int len1 = 4, len2 = 6;
    printf("Edit distance between %s and %s is %d\n", A, B, editdistance(A, len1, B, len2));
	system("pause");
    return 0;
}

调试：

求编辑距离,算法,算法,数据结构,c语言

通过运行，可知s1,s2的编辑距离4

核心代码：

for (i = 1; i <= len1; i++) {
for (j = 1; j <= len2; j++) {
if (str1[i - 1] == str2[j - 1]) {
d[i][j] = d[i - 1][j - 1];
} else {
temp = min(d[i - 1][j] + 1, d[i][j - 1] + 1);
d[i][j] = min(temp, d[i - 1][j - 1] + 1);
}
}
}

此段代码为该算法最核心部分