AcWing 902. 最短编辑距离
原题链接
简单
作者:
_如鲸向海
,
2022-06-23 23:12:28
,
所有人可见
,
阅读 175
题目描述
和y总的略有不同
算法1
C++ 代码
#include <iostream>
#include <algorithm>
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
using namespace std;
int main(){
scanf("%d%s",&n,a+1);
scanf("%d%s",&m,b+1);
for (int i = 0; i <= m; i ++ ) f[0][i] = i;
for (int i = 0; i <= n; i ++ ) f[i][0] = i;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++){
f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
if(a[i]==b[j]) f[i][j] = f[i-1][j-1];
else
f[i][j] = min(f[i][j],f[i-1][j-1]+1);
}
cout<<f[n][m]<<endl;
return 0;
}
’‘’
if(a[i]==b[j]) f[i][j] = f[i-1][j-1];
else
f[i][j] = min(f[i][j],f[i-1][j-1]+1);
f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
‘’‘
这么实现的话,你会发现最后的更新过程中只考虑到了增删两种情况。对于已经更新过的修改操作你并没有考虑进去。
那么改为这样就对了吗?
‘’‘
if(a[i]==b[j]) f[i][j] = f[i-1][j-1];
else
f[i][j] = min(f[i][j],f[i-1][j-1]+1);
f[i][j] = min(f[i][j],f[i-1][j]+1,f[i][j-1]+1);
‘’‘
也不对,因为在第一步更新的过程中,你会把f数组初始化的0带入比较,这就导致下一步更新的过程中,依旧在拿0去比较。
因为f[i][j]在更新的过程中,只会选择三种操作最小的情况进行更新,所以在实现时,不考虑a[i]和b[j]的关系是无所谓的,先确保f[i][j]被更新完不是0,之后在考虑a[i]和b[j]的关系,也可以保证每次选择最小的三种之一的操作.
佬,请问增删操作为什么要在修改操作的后面,颠倒顺序就wa,望解答
逻辑上这么实现是没问题的,但是在代码实现上就有问题。