對源串或目标串進行插入、修改、删除操作使其一緻，求最小的操作次數

問題：對源串或目标串進行插入、修改、删除操作使其一緻，求最小的操作次數

思路：兩個串分别為A[0:m],B[0:n],

對于A[0]=B[0],  f(A[0:m],B[0:n])=f(A[1:m],B[1:n])

對于A[0]!=B[0], 3種操作作用于A,B

插入：對A插入一個與B [0]相同的數， f(A[0:m],B[0:n])=f(A[0:m],B[1:n])+1

           對B插入一個與A[0]相同的數， f(A[0:m],B[0:n])=f(A[1:m],B[0:n])+1

删除：A删除與B [0]不同的數， f(A[0:m],B[0:n])=f(A[1:m],B[0:n])+1

           B删除與A[0]不同的數， f(A[0:m],B[0:n])=f(A[0:m],B[1:n])+1

修改：将A[0]修改為與B[0]相同的數， f(A[0:m],B[0:n])=f(A[1:m],B[1:n])+1

          将B[0]修改為與A[0]相同的數， f(A[0:m],B[0:n])=f(A[1:m],B[1:n])+1

總結如下：

 f(A[0:m],B[0:n])=f(A[1:m],B[1:n]) A[0]=B[0]

 f(A[0:m],B[0:n])=min{f(A[0:m],B[1:n])+1,f(A[1:m],B[0:n])+1,f(A[1:m],B[1:n])+1} A[0]!=B[0]

實作程式：

#include <iostream>
#include <string.h>

using namespace std;
int get_min(int a,int b,int c)
{
    int min_value=a;
    if(min_value>b)
        min_value=b;
    if(min_value>c)
        min_value=c;
    return min_value;
}

int cal(char *a,char *b)
{
    int lenA=strlen(a);
    int lenB=strlen(b);
    int **c=new int*[lenA+1];

    for(int i=0;i<lenA+1;i++)
    {
        c[i]=new int[lenB+1];
    }

    for(int i=0;i<lenA+1;i++)
    {
        c[i][lenB]=lenA-i;
    }

     for(int i=0;i<lenB+1;i++)
    {
        c[lenA][i]=lenB-i;
    }

    for(int i=lenA-1;i>=0;i--)
    {
        for(int j=lenB-1;j>=0;j--)
        {
            if(a[i]==a[j])
                c[i][j]=c[i+1][j+1];
            else
            {
                c[i][j]=get_min(c[i+1][j],c[i][j+1],c[i+1][j+1])+1;
            }
        }
    }

    int res=c[0][0];
    for(int i=0;i<lenA+1;i++)
        delete []c[i];
    delete c;
    return res;
}

int main()
{
    char a[100]="abdd";
    char b[100]="aebdd";

    cout << cal(a,b) << endl;
    return 0;
}
           

輸出結果：1