Linear DP acwing 902 Shortest editing distance

linear DP AcWing 902. The shortest editing distance

Original link

AcWing 902. The shortest editing distance

Algorithm tags

Dynamic programming linear DP

Ideas

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 1005, INF = 0x3f3f3f3f;
int n,m;
char A[N], B[N];
int f[N][N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n=read();
    scanf("%s", A+1);
    m=read();
    scanf("%s", B+1);
    //  if A It's empty  B Yes i Characters   Conduct i Add operations 
    rep(i, 0, m+1){
        f[0][i]=i;
    }
    //  if A Yes i Characters  B It's empty   Conduct i Delete operations 
    rep(i, 0, n+1){
        f[i][0]=i;
    }
    rep(i, 1, n+1){
        rep(j, 1, m+1){
            f[i][j]=min(f[i-1][j], f[i][j-1])+1;
            if(A[i]==B[j]){//  No replacement operation required 
                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);
            }
        }
    }
    printf("%lld", f[n][m]);
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support