最短编辑距离
题目 最短编辑距离
思路分析
原本以为又是直接变形 但是想简单了
（求出最长公共子序列的长度 把a的长度一减 就是需要操作的次数？显然没有考虑到各个位置是否匹配的问题）
那重新分析吧
还是两个序列 所以仍旧用f[i][j]的形式表示状态
现在含义有所改变：i，j表示将第一个序列 a[1~i]变成第二个序列b[1~j]的操作
属性：min
三种操作划分成三个集合
考虑状态转移的时候 先考虑如果我没有进行这个操作应该是什么状态 然后考虑你进行这一步操作之后会对你下一个状态造成什么影响 然后再加上之前状态表示中你决策出来的那个DP属性 这样就可以自然而然地搞出来转移方程了
1)删除操作：
把a[i]删掉之后a[1~i]和b[1~j]匹配
所以之前要先做到a[1~(i-1)]和b[1~j]匹配
f[i-1][j]+1
2)插入操作：
插入之后a[i]与b[j]完全匹配，所以插入的就是b[j]
那填之前a[1~i]和b[1~(j-1)]匹配
f[i][j-1] + 1
3)替换操作：
把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配
那么修改这一位之前，a[1~(i-1)]应该与b[1~(j-1)]匹配
f[i-1][j-1] + 1
但是如果本来a[i]与b[j]这一位上就相等，那么不用改，
即 f[i-1][j-1] + 0
整理出来：
for(int i=1; i<=lena; i++) {
for(int j=1; j<=lenb; j++) {
f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
if(a[i]==b[j])
f[i][j] = min(f[i][j],f[i-1][j-1]);
else
f[i][j] = min(f[i][j],f[i-1][j-1]+1);
}
}
最后考虑初始化问题
先考虑有哪些初始化
1.看在for遍历的时候需要用到的但是事先没有的
（往往就是什么0啊1啊之类的）就要预处理
2.如果要找min的话别忘了INF
要找有负数的max的话别忘了-INF
ok对应的：
1.f[0][i]如果a初始长度就是0，那么只能用插入操作让它变成b
f[i][0]同样地，如果b的长度是0，那么a只能用删除操作让它变成b
2.f[i][j] = INF //虽说这里没有用到，但是把考虑到的边界都写上还是保险
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010,INF=2e9;
int lena,lenb;
char a[N],b[N];
int f[N][N];
int main()
{
cin>>lena>>a+1>>lenb>>b+1;
//初始化
for(int i=1;i<=lena;i++)
for(int j=1;j<lenb;j++)
f[i][j]=INF;
for(int i=1;i<=lena;i++)
f[i][0]=i;
for(int j=1;j<=lenb;j++)
f[0][j]=j;
for(int i=1;i<=lena;i++)
{
for(int j=1;j<=lenb;j++)
{
f[i][j]=min({f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+(a[i]!=b[j])});
}
}
cout<<f[lena][lenb];
return 0;
}
💬 评论