蒜头君的秘密文件（编辑距离）

佚名 4年前 (2020-01-18) 随笔 2125人围观抢沙发百度已收录

每个人都有点秘密，蒜头君也不例外，他把秘密记在一个小本上，并且留有备份，不过第一个本的内容被人破坏掉了，跟原来不一定相同了，他现在想要照着第二个本把第一个本的内容还原，每一次做一个操作，一个操作可以是在某位置增加一个字符，删掉某个字符，或者把某个位置的字符改成另一个字符，他想知道他最少需要进行多少次操作才能把第一个本的内容还原。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入格式

第一行一个字符串A，表示第一个本被破坏之后的字符串。

第二行一个字符串B，表示第二个本上面的字符串。

字符串均仅有小写字母组成且长度均不超过1000。

输出格式

输出一个整数，为蒜头君最少要做的操作数。

样例输入

aa
ab

样例输出

这道题就是求由A串变为B串的编辑距离，按照编辑距离的状态转移方程进行转移就可以了。

参考另一篇博客https://www.cnblogs.com/jiamian/p/12203580.html

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int maxn=1e5+10;
16 using namespace std;
17 
18 char a[1005];
19 char b[1005];
20 int dp[1005][1005];
21 
22 int main()
23 {
24     scanf("%s %s",a,b);
25     for(int i=1;i<=strlen(a);i++)
26         dp[i][0]=i;
27     for(int i=1;i<=strlen(b);i++)
28         dp[0][i]=i;
29     for(int i=1;i<=strlen(a);i++)
30     {
31         for(int j=1;j<=strlen(b);j++)
32         {
33             if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1];
34             else dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
35         }
36     }
37     printf("%d\n",dp[strlen(a)][strlen(b)]);
38     return 0;
39 }