一、实践题目
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
(1)删除一个字符；
(2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。
对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。 输入格式: 第一行是字符串A，文件的第二行是字符串B。 提示：字符串长度不超过2000个字符。 输出格式: 输出编辑距离d(A,B) 输入样例: 在这里给出一组输入。例如： fxpimu xwrs 输出样例: 在这里给出相应的输出。例如： 5
二、问题描述
题目大意是：给出两个字符串 a、b，可以通过增删改三个操作将a变成b，需要进行几次操作。
三、算法描述
这道题类似于求最长公共子序列，但是还是更高级一点的。我用了res [2002][2002]来存储结果，res[i][j]表示a的子串(下标从0到i）转化为b的子串（下标从0到j）需要的操作次数，因此本题结果是res[strlen(a)][strlen(b)]。
那么问题就转化为求出res数组。
本题的res数组:
| a b | 空串 | x | w | r | s |
| 空串 | 0 | 1 | 2 | 3 | 4 |
| f | 1 | 1 | 2 | 3 | 4 |
| x | 2 | 1 | 2 | 3 | 4 |
| p | 3 | 2 | 2 | 3 | 4 |
| i | 4 | 3 | 3 | 3 | 4 |
| m | 5 | 4 | 4 | 4 | 4 |
| u | 6 | 5 | 5 | 5 | 5 |
1、初始化：当strlen(a)=0,res[0][j]=j;同理可得res[i][0]=i;
2、当a[i-1]=b[j-1],则res[i][j]=res[i-1][j-1]，即等于左上角的元素;
3、当a[i-1]!=b[j-1]，有以下三种情况：
（1）若进行删除操作：操作数加1，res[i][j]=res[i-1][j]+1;
（2）若进行增加操作：操作数加1，res[i][j]=res[i][j-1]+1;
（3）若进行替换操作：操作数加1，res[i][j]=res[i-1][j-1]+1;
res[i][j]等于上面三种情况res[i][j]里的最小值
通过以上分析，我们可以发现填表规则是从上到下从左往右填一个大小为strlen(a)*strlen(b)的表格，两层for循环对res数组操作：匹配时取左上的值；
失配时取 左上+1，左边+1，右边+1 三个数中的最小值，更新res[i]][j];
最后递推到右下角dp[la][lb]为所求答案
代码如下：
1 #include<iostream> 2 #include<string.h> 3 using namespace std; 4 char a[2005], b[2005]; 5 int res [2002][2002]; 6 int temp = 1; 7 int main (){ 8 cin >> a; 9 cin >> b; 10 int la = strlen (a); 11 int lb = strlen (b); 12 for(int i = 0; i <= la; i++) res[i][0] = i; 13 for(int i = 0; i <= lb; i++) res[0][i] = i; 14 15 for(int i = 1; i <= la; i++){ 16 for(int j = 1; j <= lb; j++){ 17 if(a[i-1] == b[j-1]) temp = 0; else temp = 1; 18 int t = min(res[i-1][j] + 1,res[i][j-1] + 1); 19 res[i][j] = min(t,res[i-1][j-1] + temp); 20 } 21 } 22 23 cout << res[la][lb]; 24 return 0; 25 }
四、算法时间及空间复杂度分析
采用dp思想，两层for循环处理res数组，故时间复杂度为O（n^2）
五、心得体会
dp问题最重要的还是要找到问题的最优解子结构，然后建立递推关系，确定好填表的顺序。
多打题，才能提高、加深对算法的理解。