题意
给出两个字符串A,B,三种操作:
- 删除A中某个字符
- A中插入一个字符
- 修改A中某个字符
问将A变成B最小的操作步数。
思路
dp[i][j]表示将A[1~i]变成B[1~j]的最小步数
状态转移:
对于每个A[i],有三种操作:
删除A[i],dp[i][j]=dp[i-1][j]+1
A[i]后面插入B[j],dp[i][j]=dp[i][j-1]+1
如果A[i]!=b[j],修改A[i]为B[j],dp[i][j]=dp[i-1][j-1]+1
三种操作方式对于不同的状态转移。
特别注意的是,即使A[i]==B[j]
,也不能将dp[i][j]=dp[i-1][j-1]
,当strlen(A)>strlen(B)时,会出现反例
。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
char a[maxn],b[maxn];
int f[maxn][maxn];
int n,m;
int main(){
cin>>n>>(a+1);
cin>>m>>(b+1);
for(int i=1;i<=m;i++)f[0][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],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];
return 0;
}