# ACwing 902最短编辑距离 (线性dp)

题意

给出两个字符串A,B,三种操作:

  1. 删除A中某个字符
  2. A中插入一个字符
  3. 修改A中某个字符

问将A变成B最小的操作步数。

思路

dp[i][j]表示将A[1~i]变成B[1~j]的最小步数

状态转移:

对于每个A[i],有三种操作:

  1. 删除A[i],dp[i][j]=dp[i-1][j]+1
  2. A[i]后面插入B[j],dp[i][j]=dp[i][j-1]+1
  3. 如果A[i]!=b[j],修改A[i]为B[j],dp[i][j]=dp[i-1][j-1]+1

三种操作方式对于不同的状态转移。

特别注意的是,即使A[i]==B[j],也不能将dp[i][j]=dp[i-1][j-1],当strlen(A)>strlen(B)时,会出现反例

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
char a[maxn],b[maxn];
int f[maxn][maxn];
int n,m;

int main(){
    cin>>n>>(a+1);
    cin>>m>>(b+1);
    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],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];
    return 0;
}

# ACwing 902最短编辑距离 (线性dp)

上一篇:# ACwing 282 石子合并(区间dp)


下一篇:# Acwing 1086 腾讯编程马拉松 恨7不成妻(数位dp维护多个值+数学转换)