最短编辑距离

**编辑距离里看转移，本质就是看“最后一步消耗了谁” ** by Codex

tag: 线性DP

题目背景：给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

1. 删除–将字符串 A 中的某个字符删除。
2. 插入–在字符串 A 的某个位置插入某个字符。
3. 替换–将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A 变为 B 至少需要进行多少次操作。

集合: 将 $a[1 \sim i]$ 变成 $b[1\sim i]$ 的操作方式

属性: min

状态计算:

• 删除操作: 将 $a[i]$ 删掉后 $a[1\sim i]$ 和 $b[1\sim j]$ 匹配, 所以需要在此之前完成 $a[1\sim (i-1)]$ 和 $b[1\sim j]$ 的匹配, 因此最后的结果是 $dp[i-1][j]+1$
• 插入操作: 插入后 $a[1\sim i]$ 和 $b[1\sim j]$ 匹配, 所以需要消耗 $b[j]$ , 因此要先完成 $a[i\sim i]$ 和 $b[1\sim (j-1)]$ 的匹配, 因此最后的结果是 $dp[i][j-1]+1$ (具体来说, 就是1i 变为 1j 是由1i 变为1(j-1) 后加一个 $b[j]$ 得到的)
• 替换操作: 将 $a[i]$ 改成 $b[j]$ 后想要 $a[1\sim i]$ 和 $b[1\sim j]$ 匹配, 需要使 $a[1\sim (i-1)]$ 和 $b[1\sim (j-1)]$ 匹配, 然后判断 $a[i]$ 是否等于 $b[j]$ , 如果相等就不用加1, 不等就加1.

代码：

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;

int dp[N][N];
int n,m;
char a[N],b[N];

int main()
{
    cin>>n>>a+1>>m>>b+1;
    for(int i=0;i<=n;i++)dp[i][0]=i;//删除i步
    for(int i=0;i<=m;i++)dp[0][i]=i;//增加i步
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//先用增删更新
            if(a[i]==b[j])dp[i][j]=min(dp[i][j],dp[i-1][j-1]);//再用替换更新
            else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
        }
    cout<<dp[n][m];
    return 0;
}