2709 - 编辑距离
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。
对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
Input
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。
Output
只有一个正整数，为最少字符操作次数。
Examples
Input
sfdxbqw gfdgw
Output
4
Solution C
#include <stdio.h> #include <string.h> #define min(a,b) (a<b?a:b) char str1[3100],str2[3100]; int dp[3100][3100]; int main() { int i,j,t,len1,len2; while(~scanf("%s%s",str1,str2)) { len1 = strlen(str1); len2 = strlen(str2); for( i=0; i<=len1; i++) dp[i][0] = i; for( j=0; j<=len2; j++) dp[0][j] = j; for( i=1; i<=len1; i++) { for( j=1; j<=len2; j++) { t = (str1[i-1] == str2[j-1])?0:1; dp[i][j] = min(dp[i-1][j-1] + t, dp[i-1][j]+1); dp[i][j] = min(dp[i][j],dp[i][j-1]+1); } } printf("%d",dp[len1][len2]); } return 0; }
Solution C++
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; char str1[3100],str2[3100]; int dp[3100][3100]; int main() { while(~scanf("%s%s",str1,str2)) { int len1 = strlen(str1); int len2 = strlen(str2); for(int i=0; i<=len1; i++) dp[i][0] = i; for(int j=0; j<=len2; j++) dp[0][j] = j; for(int i=1; i<=len1; i++) { for(int j=1; j<=len2; j++) { int t = (str1[i-1] == str2[j-1])?0:1; dp[i][j] = min(dp[i-1][j-1] + t, dp[i-1][j]+1); dp[i][j] = min(dp[i][j],dp[i][j-1]+1); } } printf("%d",dp[len1][len2]); } return 0; }