TIOJ 1385 芳佳的打工

poao899    3944K    120MS    G++    0.37K     2009-10-26 22:29:48                                              .

唔記憶體差蝴蝶一點點Q


編輯距離。

詳見wiki：編輯距離(English)

是說一開始那個初始化炸掉超不甘心的

還沒找到反例(?

//**********************************

#include<stdio.h>
int dp[1001][1001],i,j;
char a[1001],b[1001];
main(){
    gets(a+1);
    gets(b+1);
    for(i=1;a[i];i++)
        dp[i][0]=i;
    for(j=1;b[j];j++)
        dp[0][j]=j;
    for(i=1;a[i];i++)
        for(j=1;b[j];j++){
            dp[i][j]=(dp[i-1][j]<?dp[i][j-1])+1;
            dp[i][j]<?=(dp[i-1][j-1]+(a[i]!=b[j]));
            //printf("%d %d:%d\n",i,j,dp[i][j]);
        }
    printf("%d\n",dp[i-1][j-1]);
}



延伸：

1.滾動?

2.找出如果

    for(i=1;i<1001;i++)
        dp[i][0]=i;
    for(j=1;j<1001;j++)
        dp[0][j]=j;

反例
反例