题目描述

902.最短编辑距离
这道题我们也是用dp
其中f[i][j]表示将a中的前i个字母与b中的前j个字母相同所用的操作方式
我们要取最小值
我们可以有三种操作
(1) 删除第a中第i个字母 使得他们a中前i个与b中前j个相等 这个时候表示a(1~(i-1))与b(1~j)中的字母相同，即这个时候f[i][j] =f[i-1][j] +1;
(2) 添加a中第i个字母使得他们相同这个时候表示a(1~i)与b(1~(j-1))相同，即这个时候我们的状态表示为f[i][j] =f[i][j-1] +1
(3) 对于替换操作这个时候我们还能再分两种情况
1. 当a[i]==b[j] 这个时候不用替换f[i][j] =f[i-1][j-1]
2. 当不相等的时候 替换完后相等表示a(1~(n-1))与b(1~(n-1))相等
这个时候f[i][j] =f[i-1][j-1]+1;
对上面的情况我们取最小值就行 所以我们要初始区域内趋于无穷大 因为哦我们要取最小值
我们还要初始
f[i][0]=i表示我们必须要用删除i次的方法才能让他们相同
f[0][j]=j 表示我们必须要用添加j次的方法才能让他们相同 对这些的数据初始化的时候我们记得将从0开始 我们的f数组是从0开始的
在存字符串的时候我们记得要a，b数组都是字符型的数组
最后我们输出f[n][m]就表示a的序列变成b的序列需要最小操作数为多少了

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =1010;
int f[N][N];
char a[N], b[N];
int n, m;
int main()
{
    cin>>n>>a+1>>m>>b+1;
    memset(f,0x3f3f3f,sizeof f);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            f[i][0] =i;
            f[0][j] =j;
        }

    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]<<endl;
    return 0;

}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla