动态规划之编辑距离问题*

「爱情、让人受尽委屈。」 2022-04-22 02:08 210阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NjA1MzI4_size_16_color_FFFFFF_t_70][]

由公式可以看出，(i-1,j)对应删除操作，(i,j-1)对应插入操作。  
可以这样理解，现在耗费了di-1,j步操作将字符串a(1,i-1)转换成了b(1,j)，则在将a(1,i)转换成b(1,j)时，我们可以直接删掉字符a(i)，  
问题变成a(1,i-1)转换成b(1,j)，从而dij就等于di-1,j+1。同理，现在耗费了di,j-1步操作将字符串a(1,i)转换成了b(1,j-1)，  
则在将a(1,i)转换成b(1,j)时，我们可以将b(j)添加到a(1,i)末尾（此时a(1,i)已转换成b(1,j-1)）构成b(1,j)。对应的代码实现如下：

\#include <stdio.h>  
\#include <stdlib.h>  
\#include <string.h>  
int dist\[100\]\[100\];//表示长度为i的字符串变为长度为j的字符串需要的编辑距离  
int MIN(int i,int j)  
\{  
    if(i>j)  
        return j;  
    else  
        return i;  
\}  
int edit\_distance(char\* a,char\* b)  
\{  
    int i,j;  
    int len\_a=strlen(a);  
    int len\_b=strlen(b);  
    printf("%d %d \\n",len\_a,len\_b);  
    //b为空字符串，将a变为b需要不停地删除a的字符  
    for ( i=0;i<=len\_a;i++)  
    \{  
        dist\[i\]\[0\]=i;  
    \}

//a为空字符串，将a变为b需要不停地添加b的字符  
    for ( j=0;j<=len\_b;j++)  
    \{  
        dist\[0\]\[j\]=j;  
    \}

for ( i=1;i<=len\_a;i++)  
    \{  
        for ( j=1;j<=len\_b;j++)  
        \{  
            int cost = (a\[i-1\] == b\[j-1\] ? 0 : 1);      /\*\*\*\*\*\*/

int deletion = dist\[i-1\]\[j\] + 1;         //删除  
            int insertion = dist\[i\]\[j-1\] + 1;        //插入  
            int substitution = dist\[i-1\]\[j-1\] + cost;//变换/不动

dist\[i\]\[j\] = MIN(deletion,MIN(insertion,substitution));  
        \}  
    \}

for(i=0;i<=len\_a;i++)  
    \{  
        for(j=0;j<=len\_b;j++)  
        \{  
            printf("%d ",dist\[i\]\[j\]);  
        \}  
        printf("\\n");  
    \}  
    return dist\[len\_a\]\[len\_b\];  
\}

int main()  
\{  
    char a\[8\] = "abc";  
    char b\[6\] = "cba";  
    int result = edit\_distance(a,b);  
    printf("%d\\n",result);

//printf("%d\\n",dist\[1\]\[1\]);  
    return 0;  
\}--

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NjA1MzI4_size_16_color_FFFFFF_t_70]: /images/20220422/07583691117b4b2c99c3ca811974a5e9.png