思路
- 分析如下:
-
注意需要将边界 $f[i][0]$ 和 $f[0][i]$ 初始化为 $i$ 。
-
时间复杂度为 $O(MN)$ ,空间复杂度为 $O(MN)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char s1[N],s2[N];
int f[N][N];
int main(void){
int n,m,i,j;
scanf("%d%s%d%s",&n,&s1[1],&m,&s2[1]);
for(i=1;i<=n;i++){
f[i][0]=i;
}
for(i=1;i<=m;i++){
f[0][i]=i;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
f[i][j]=min({f[i-1][j],f[i][j-1],f[i-1][j-1]})+1;
if(s1[i]==s2[j]){
f[i][j]=min(f[i][j],f[i-1][j-1]);
}
}
}
printf("%d\n",f[n][m]);
return 0;
}