AcWing 902. 最短编辑距离
原题链接
简单
作者:
当下LYC
,
2024-02-26 19:17:04
,
所有人可见
,
阅读 21
题目描述
样例
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1010;
char a[N],b[N];
int f[N][N];
int main()
{
int n,m;
scanf("%d%s",&n,a + 1);
scanf("%d%s",&m,b + 1);
for(int i = 1 ; i <= n ; i++) f[i][0] = i;//初始化操作
for(int i = 1 ; i <= m ; i++) f[0][i] = 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[i]) f[i][j] = min(f[i-1][j-1] + 1 , f[i][j]); 写不下去了QWQ,而且错了
if(a[i] == b[j]) f[i][j] = min(f[i-1][j-1] , f[i][j]);//对于括号第一项来说,
//后面已经没它什么事儿了~
else f[i][j] = min(f[i-1][j-1] + 1,f[i][j]);
}
printf("%d\n",f[n][m]);
return 0;
}