程式碼備份區

題意：

給兩個長度以及他們的字串，求他們的Edit Distance

解法：

用Edit Distance

這邊是Bottom up的填表方法

程式碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MIN(x,y)(((x)<(y))?(x):(y))
#define INF 1<<29
int aLen,bLen;
char a[1001];
char b[1001];

int dp[1001][1001];

int findBU(int aLen,int bLen){
    int i,j;
    for(i=1;i<=aLen;++i)dp[i][0] = i;
    for(j=1;j<=bLen;++j)dp[0][j] = j;
    dp[0][0] = 0;

    for(i=1;i<=aLen;++i){
        for(j=1;j<=bLen;++j){
            if(a[i]==b[j])dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = MIN(dp[i-1][j-1],MIN(dp[i-1][j],dp[i][j-1]))+1;
        }
    }

    return dp[aLen][bLen];
}


int main(){

    while(scanf("%d %s",&aLen,&a[1])!=EOF){
        scanf("%d %s",&bLen,&b[1]);
        printf("%d\n",findBU(aLen,bLen));
    }

    return 0;
}