算法介绍

状态表示：f[i][j]表示在A字符串前i个字符，B字符串前j个字符的基础上如何做操作，使得操作后的两串相等，需要的所有种可能的操作序列的集合 属性是操作次数的最小值
状态计算：
1.在A[1~i]和B[1~j]的基础上，经过删除第i个元素后，A[1~i]才和B[1~j]相同(说明A[1~i-1]已经和B[1~j]相同)
int del=f[i-1][j]+1;
2.在A[1~i]和B[1~j]的基础上，经过在i后添加1个元素后，A[1~i+1]才和B[1~j]相同(说明A[1~i]已经与B[1~j-1]相同)
int zeng=f[i][j-1]+1;
3.经过更改第i个元素后，A[1~i]才和B[i~j]相同(说明A[1~i-1]==B[1~j-1])
3.1若A[i]==B[j] 岂不是可以省去这一步操作？
int gai=f[i-1][j-1];
3.2若A[i]!=B[j],就要加上修改这一步操作
int gai=f[i-1][j-1]+1;

代码

195ms

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<string>
int main(void){
    int n,m;
    string A,B;
    cin>>n>>A>>m>>B;
    A=" "+A,B=" "+B;
    int f[n+1][m+1];//f[i][j]表示把A字符串前i个字符变成B字符串前j个字符需要的所有套可能的操作的集合 属性是操作次数的最小值
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i][0]=i;//把A的前i个字符与B的前0个字符匹配只能采用“删除”的方式来操作，前几个字符就删除几个，操作次数为i
    for(int j=1;j<=m;j++) f[0][j]=j;//把A的前0个字符与B的前j个字符匹配只能采用“添加”的方式来操作，前几个字符就添加几个，操作次数为j
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){ 
            int del=f[i-1][j]+1;
            int zeng=f[i][j-1]+1;
            int gai;
            if(A[i]==B[j]) gai=f[i-1][j-1];
            else gai=f[i-1][j-1]+1;
            f[i][j]=min({del,zeng,gai});
        }
    }
    cout<<f[n][m];
}

时间优化版本代码

133ms
memset()–》改为从0开始初始化
min({a,b,c})-》改为两次min(a,b),min(a,c)

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<string>
int main(void){
    int n,m;
    string A,B;
    cin>>n>>A>>m>>B;
    A=" "+A,B=" "+B;
    int f[n+1][m+1];//f[i][j]表示把A字符串前i个字符变成B字符串前j个字符需要的所有套可能的操作的集合 属性是操作次数的最小值
    // memset(f,0,sizeof(f));
    for(int i=0;i<=n;i++) f[i][0]=i;//把A的前i个字符与B的前0个字符匹配只能采用“删除”的方式来操作，前几个字符就删除几个，操作次数为i
    for(int j=0;j<=m;j++) f[0][j]=j;//把A的前0个字符与B的前j个字符匹配只能采用“添加”的方式来操作，前几个字符就添加几个，操作次数为j
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){ 
            // int del=f[i-1][j]+1;
            // int zeng=f[i][j-1]+1;
            // int gai;
            // if(A[i]==B[j]) gai=f[i-1][j-1];
            // else gai=f[i-1][j-1]+1;
            // f[i][j]=min({del,zeng,gai});
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            f[i][j]=min(f[i][j],f[i-1][j-1]+(A[i]!=B[j]));
        }
    }
    cout<<f[n][m];
}