거리 편집(dp)

동적 이동 방정식은 세 가지 절차에 따라 f[i-1][j-1], f[i-1][j], f[i][j-1]+1에서 옮겨오기 때문에 f[i][j]=min(f[i-1][j-1], f[i-1][j], f[j], f[i][j-1])+1이다.

#include<cstdio>
#include<cstring> 
#include<iostream>
using namespace std;
char a[9999],b[9099];
int f[3999][3999];
int main() {
    gets(a);
    gets(b);
    int lena=strlen(a);
    int lenb=strlen(b);
    for(int i=0;i<lena;i++)
    f[i][0]=i;
    for(int i=0;i<lenb;i++)
    f[0][i]=i;
    for(int i=1;i<=lena;i++)
    {
        for(int j=1;j<=lenb;j++)
    {
        if(a[i-1]==b[j-1])
        f[i][j]=f[i-1][j-1];
        else{
            f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
        }
        //printf("%d ",f[i][j]);
    }
    //printf("
");
    }
    printf("%d",f[lena][lenb]/*+lena-lenb*/);
}