题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

/*
这道题卡住的地方有一个是因为思维没有转换
比如AB->ATB 一直在想怎么从中间插入
其实算的时候因为A'B'==AT'B' B相等 转换为A->AT需要的最少步数即可
而A->AT只需要插入T 但是看起来的结果是在A和B中间插入的
*/
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int m,n;
string a,b;
int f[1002][1002];
int main()
{
    cin>>m>>a>>n>>b;
    memset(f,0,sizeof(f));
    for(int j=0;j<=n;j++) f[0][j]=j;
    for(int j=0;j<=m;j++) f[j][0]=j;

    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1];
            else f[i][j]=min(min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+1);
        }
    }


    cout<<f[m][n]<<endl;

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla