题解 P2758 【编辑距离】

对，这道题难度怎么可能只有普及- 这是一道经典的动归题，琢磨透了思路，也就不难了 首先还是看看动归的精髓——状态转移方程式怎么来的好了 我们需要转移的，是最小编辑距离，而与之有关的，便是两行字符串了，我们分别把他们叫做初始字符串和目标字符串 所以可以以编辑到的字符串的位置来计算编辑距离 那么需要定义一个二维数组f[i][j]表示从初始字符串的前i个编辑到目标字符串的前j个的最短距离 因为这是动归题O\_\_O "… 所以可知没步的状态之和前面有关，那么在草稿纸上找啊找，重要找到了规律 f[i][j]=mini(f[i-1][j-1]+r,f[i-1][j]+1,f[i][j-1]+1); 好吧，来j解释下这个方程式：mini最好自己打，因为有些版本的c++不认min()函数的 (⊙o⊙) 在编辑初始串前i个至目标串前j个时，不难发现它的最小值为编辑前i-1初始串至j-1目标串的次数加r(当a[i]==b[j]两字符一样时不用编辑，此时r=0，当其不等时要编辑，此时r=1)和编辑前i-1初串至j标串+1（增加一个字符）和编辑前i初串至前j-1标串+1（减去一个字符）三者的最小值 如此这个动归题便完成了 PS:register 是一个玄乎的东东，yyb大佬称之卡常数（就是可以提高运行速度，避免超时，于是乎你看见了么，我的代码跑得还算快的） 希望对你有帮助！ ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int mini(int a,int b,int c) { if(a>=b&&b>=c) return c; if(a>=c&&c>=b) return b; if(b>=c&&c>=a) return a; if(b>=a&&a>=c) return c; if(c>=a&&a>=b) return b; if(c>=b&&b>=a) return a; } char a[2001],b[2001]; int f[2001][2001];//f[i][j]表示从初始字符串的前i个编辑到目标字符串的前j个的最短距离 int main() { gets(a);//初始字符串 gets(b);//目标字符串 register int lena=strlen(a),lenb=strlen(b); //进行一些初始化 for(register int i=lena;i>=1;i--) a[i]=a[i-1]; for(register int i=lenb;i>=1;i--) b[i]=b[i-1];//为方便将每个字符串的初始位置挪到1来 for(register int i=0;i<=lena;i++) f[i][0]=i;//从i个字符删到0个需执行i次 for(register int i=0;i<=lenb;i++) f[0][i]=i;//从0个字符增到i个需执行i次 //开始动归啦~\(≧▽≦)/~ //先让我们找到动归的状态转移方程式： //从初始字符串的前i位编辑成目标字符串的前j位的最小编辑次数 //会等于从其初始的前i-1位编辑成j-1位的最小次数+1(a[i]!=b[j])+0(a[i]=b[j]) //和编辑前i位成j-1位的次数+1(加一位)和编辑前i-1位和j位的次数+1的最小值(删一位) for(register int i=1;i<=lena;i++)//枚举初始字符串的长度 for(register int j=1;j<=lenb;j++)//枚举目标字符串 ``` {//上述两重循环的次序可调换（草稿纸上可以模拟出来） ```cpp register int r=0; if(a[i]!=b[j]) r=1; f[i][j]=mini(f[i-1][j-1]+r,f[i-1][j]+1,f[i][j-1]+1); } cout<<f[lena][lenb]; return 0; } ```