算法基础之最短编辑距离

最短编辑距离

• 核心思想 ： 线性dp

  • 集合定义 ： f[i][j]为操作方式的最小值

  • 集合计算 : 三种操作 取最小

    • ① 删除 : 将a[i]删掉 使ab相同 –> f[i-1][j] + 1 = f[i][j]
    • ② 增添 : 在a[i]后加上一个数 使ab相同 –> f[i][j-1] + 1 = f[i][j]
    • ③ 替换 : 将a[i] 换成 b[j] 使ab相同 若a[i] == b[j] 则不用操作
      • ​ 若!= 则 f[i-1][j-1] + 1 = f[i][j]

  • 

    •   #include<iostream>
        #include<algorithm>
        #include<cstring>
        
        using namespace std;
        const int N = 1010;
        
        int n,m;
        char a[N],b[N];
        int f[N][N];
        
        int main()
        {
               
            cin>>n>>a+1>>m>>b+1;
            //初始化 因为求的是最小值 所以初始0的话结果会错
            //第一个是 a是空的 添加m次 和b相同
            //第二个是 a是非空的 删除n次 和b相同
            for(int i=1;i<=m;i++) f[0][i] = i;
            for(int i=1;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];
        }
      

  一点思考 : 为什么确定删掉a[i]就能使a[i-1] 和 b[j] 相等 ？

  ​ 因为在求a[i-1]时 已经从概念上使它和b[j]相等 (不等的话操作次数+1 然后就等了)

  ​