PKU 3356-AGTC
問題概要
二つの文字列の編集距離を求めよ。複数ケースあるので注意
解法
編集距離をDPで求める。
詳しくはレーベンシュタイン距離 - Wikipediaを詳細。
実装(C++)
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int n,m; int dp[1001][1001]; char x[1001],y[1001]; int main() { while(~scanf("%d%s%d%s",&n,x,&m,y)){ memset(dp,0x7F,sizeof(dp)); dp[0][0]=0; for(int i=0;i<=n;i++){ dp[i][0]=i; } for(int j=0;j<=m;j++){ dp[0][j]=j; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int cost=(x[i-1]!=y[j-1]); dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+cost)); } } printf("%d\n",dp[n][m]); } return 0; }