最短编辑距离问题分析思路:
状态表示f[i][j]:
表示的集合是 所有将a[1…i]变为b[1…j]的操作方式的集合
属性是操作次数的最小值
状态计算:
根据对a[i]的操作,可分为删、增、改
删a[i]:
此时a[1…i-1]与b[1…j]中字符相等,删去a[i]
状态表示为f[i-1][j]+1
(+1表示删除操作这一步)
增a[i]:
此时a[1…i]与b[1,,,j-1]相等,加上a[i]
状态表示为:f[i][j-1]+1
改a[i]
此时a[1…i-1]与b[1…j-1]相等,分情况讨论:
若a[i]==b[j]
则状态表示为f[i-1][j-1]+0
若a[i]!=b[j]
则状态表示为f[i-1][j-1]+1
初始化问题:
for(int i=1;i<=m;i++) f[0][i]=i;//a长度为0,变换到b[i]需要i步操作
for(int i=1;i<=n;i++) f[i][0]=i;//理由同上
状态转移方程:
在上述三种情况中取min即可
代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int f[N][N];
char a[N],b[N];
int main (){
cin>>n>>a+1;
cin>>m>>b+1;
//初始化
for(int i=1;i<=m;i++) f[0][i]=i;//a长度为0,变换到b[i]需要i步操作
for(int i=1;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]=min(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;
}
字符数组从1开始存储是习惯问题,方便思考.