---

思路

给定两个字符串 A和 B，现在要将 A经过若干操作变为 B，可进行的操作有删除–将字符串 A中的某个字符删除。插入–在字符串 A的某个位置插入某个字符。替换–将字符串 A中的某个字符替换为另一个字符。

状态表示

字符串1 : a; 字符串2 : b。
f[i][j]=>表示考虑a[1~i]转变为b[1~j]需要的最少操作步数
如 a 变为 abb 需要增添两个b,即f[1][3]=2

状态计算

1.删: 当前需要删除a的最后一个字符才能和b[1~j]进行匹配的话
那么说明a[1~i-1]和b[1~j]是匹配的
2.增:当前需要在a的最后一个字符后面加一个字符才能和b[1~j]进行匹配的话,那么说明a[1~i]和b[1~j-1]是匹配的
3.改:当前需要修改a当前一个字符,那么说明a[i-1]和b[i-1]是匹配的
f[i][j]=f[i-1][j]+1 删
f[i][j]=f[i-1][j]+1 增
f[i][j]=f[i-1][j-1]+1 改

完整代码

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N =1010;
char a[N],b[N];
int f[N][N];
int n,m;

int main(){
    cin>>n;
    scanf("%s",a+1);
    
    cin>>m;
    scanf("%s",b+1);

    //初始化->a的前0个字母匹配b,只能进行添加操作
    for(int i=0; i<=m; i++)f[0][i]=i;
    //同理,b的前0个字母匹配a,添加
    for(int i=0; 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];
    
    return 0;
}

结语

---

🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻

🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹

😇 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 😇

---