2233 - 字符串的修改
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。
对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
题目输入
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。
题目输出
只有一个正整数，为最少字符操作次数。
输入/输出样例
题目输入
sfdxbqw gfdgw
题目输出
4
C++解答
// 动态规划实现 最小编辑距离 #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #define SENTINEL (-1) #define EDIT_COST (1) #include<algorithm> using namespace std; // Returns Minimum among a, b, c int Minimum(int a, int b, int c) { return min(min(a, b), c); } // Strings of size m and n are passed. // Construct the Table for X[0...m, m+1], Y[0...n, n+1] int EditDistanceDP(char X[], char Y[]) { // Cost of alignment int cost = 0; int leftCell, topCell, cornerCell; int m = strlen(X)+1; int n = strlen(Y)+1; // T[m][n] int *T = (int *)malloc(m * n * sizeof(int)); // Initialize table for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) *(T + i * n + j) = SENTINEL; // Set up base cases // T[i][0] = i for(int i = 0; i < m; i++) *(T + i * n) = i; // T[0][j] = j for(int j = 0; j < n; j++) *(T + j) = j; // Build the T in top-down fashion for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { // T[i][j-1] leftCell = *(T + i*n + j-1); leftCell += EDIT_COST; // deletion // T[i-1][j] topCell = *(T + (i-1)*n + j); topCell += EDIT_COST; // insertion // Top-left (corner) cell // T[i-1][j-1] cornerCell = *(T + (i-1)*n + (j-1) ); // edit[(i-1), (j-1)] = 0 if X[i] == Y[j], 1 otherwise cornerCell += (X[i-1] != Y[j-1]); // may be replace // Minimum cost of current cell // Fill in the next cell T[i][j] *(T + (i)*n + (j)) = Minimum(leftCell, topCell, cornerCell); } } // 结果存储在 T[m][n] cost = *(T + m*n - 1); free(T); return cost; } // 递归方法实现 /*int EditDistanceRecursion( char *X, char *Y, int m, int n ) { // 基本情况 if( m == 0 && n == 0 ) return 0; if( m == 0 ) return n; if( n == 0 ) return m; // Recurse int left = EditDistanceRecursion(X, Y, m-1, n) + 1; int right = EditDistanceRecursion(X, Y, m, n-1) + 1; int corner = EditDistanceRecursion(X, Y, m-1, n-1) + (X[m-1] != Y[n-1]); return Minimum(left, right, corner); }*/ int main() { char s1[205],s2[205]; while(cin>>s1>>s2) { cout<<EditDistanceDP(s1,s2)<<endl; } }