---
title: "最短编辑距离"
created: 2025-11-28
tags:
  - 算法
---

# 最短编辑距离

## 题目 [最短编辑距离](https://www.acwing.com/problem/content/904/)

![[image-4e8ab99e.png]]

## 思路分析

原本以为又是直接变形 但是想简单了

（求出最长公共子序列的长度 把a的长度一减 就是需要操作的次数？显然没有考虑到各个位置是否匹配的问题）

那重新分析吧

还是两个序列 所以仍旧用f[i][j]的形式表示状态

现在含义有所改变：i，j表示将第一个序列 a[1~i]变成第二个序列b[1~j]的操作

属性：min

三种操作划分成三个集合

考虑状态转移的时候 先考虑如果我没有进行这个操作应该是什么状态 然后考虑你进行这一步操作之后会对你下一个状态造成什么影响 然后再加上之前状态表示中你决策出来的那个DP属性
这样就可以自然而然地搞出来转移方程了

1)删除操作：

把a[i]删掉之后a[1~i]和b[1~j]匹配

所以之前要先做到a[1~(i-1)]和b[1~j]匹配

f[i-1][j]+1

2)插入操作：

插入之后a[i]与b[j]完全匹配，所以插入的就是b[j]

那填之前a[1~i]和b[1~(j-1)]匹配

f[i][j-1] + 1

3)替换操作：

把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配

那么修改这一位之前，a[1~(i-1)]应该与b[1~(j-1)]匹配

f[i-1][j-1] + 1

但是如果本来a[i]与b[j]这一位上就相等，那么不用改，

即 f[i-1][j-1] + 0

整理出来：

```cpp
for(int i=1; i<=lena; i++) {
    for(int j=1; j<=lenb; 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);
    }
}
```

最后考虑初始化问题

先考虑有哪些初始化

1.看在for遍历的时候需要用到的但是事先没有的

（往往就是什么0啊1啊之类的）就要预处理

2.如果要找min的话别忘了INF

要找有负数的max的话别忘了-INF

ok对应的：

1.f[0][i]如果a初始长度就是0，那么只能用插入操作让它变成b

f[i][0]同样地，如果b的长度是0，那么a只能用删除操作让它变成b

2.f[i][j] = INF //虽说这里没有用到，但是把考虑到的边界都写上还是保险

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010,INF=2e9;

int lena,lenb;

char a[N],b[N];

int f[N][N];

int main()

{

    cin>>lena>>a+1>>lenb>>b+1;

    //初始化

    for(int i=1;i<=lena;i++)

        for(int j=1;j<lenb;j++)

            f[i][j]=INF;

    for(int i=1;i<=lena;i++)

        f[i][0]=i;

    for(int j=1;j<=lenb;j++)

        f[0][j]=j;

    for(int i=1;i<=lena;i++)

    {

        for(int j=1;j<=lenb;j++)

        {

            f[i][j]=min({f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+(a[i]!=b[j])});

        }

    }

    cout<<f[lena][lenb];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[接龙序列|接龙序列]] 🏠 [[00-刷题理模型]] ➡️ [[最长上升子序列|最长上升子序列]]