はなたの日記

ギターのコードについて書きます

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;
}

動的計画法の肝は漸化式だと思うのですが、漸化式を自分で立てられないのマズイなあと思いました。自分で立てれらるようになりたいです。