AcWing 902. 最短编辑距离
原题链接
简单
状态转移方程和最大公共子序列很像,原理不同//
此类转移方程的变动值来源于f[i][j]=min(f[i][j],f[i-1][j-1]+1);
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int nn=1010;
char sa[nn],sb[nn];
int f[nn][nn];
int n,m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>sa+1;
cin>>m>>sb+1;
//初始化//
for(int i=0;i<=n;i++)//存储最大交换次数//
f[i][0]=i;
for(int j=0;j<=m;j++)//存储最大交换次数//
f[0][j]=j;
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(sa[i]==sb[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;//将n转变为m需要的最少步数//
return 0;
}