DPL_1_E Edit Distance (Levenshtein Distance)
問題
Edit Distance (Levenshtein Distance) | Aizu Online Judge
文字列の編集距離の問題です。動的計画法で解きます。以下のページが分かり易かったです。
d.hatena.ne.jp
#include<stdio.h> #include<string.h> #include<stdlib.h> #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define LARGE 1001 int Get_min(int a,int b,int c){ int x=MIN(a,b); int y=MIN(b,c); return MIN(x,y); } int main(){ char s1[LARGE]; char s2[LARGE]; int m,n; int i,j; int **dp; scanf("%s",s1); scanf("%s",s2); m=strlen(s1)+1; n=strlen(s2)+1; dp=malloc(sizeof(int*)*m); for(i=0;i<m;i++){ dp[i]=malloc(sizeof(int)*n); for(j=0;j<n;j++)dp[i][j]=0; } for(i=0;i<m;i++)dp[i][0]=i; for(i=0;i<n;i++)dp[0][i]=i; for(i=1;i<m;i++){ for(j=1;j<n;j++){ if(s1[i-1]==s2[j-1])dp[i][j]=Get_min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]); else dp[i][j]=Get_min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1); } } printf("%d\n",dp[m-1][n-1]); return 0; }
動的計画法の肝は漸化式だと思うのですが、漸化式を自分で立てられないのマズイなあと思いました。自分で立てれらるようになりたいです。