526互联

luogu_P2758 编辑距离

发布时间 2023-04-27 15:55:19作者: Miburo

P2758 编辑距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

设 AA 和 BB 是两个字符串。我们要用最少的字符操作次数，将字符串 AA 转换为字符串 BB。这里所说的字符操作共有三种：

  1. 删除一个字符；
  2. 插入一个字符；
  3. 将一个字符改为另一个字符。

A,B 均只包含小写字母

思路：dp[i][j]表示A的1到i字串变为B的1到i字串需要的最少操作。    dp[i][j]=min(dp[i][j],min(dp[i-1][j-1]+1, min(dp[i-1][j]+1,dp[i][j-1]+1)));
string A,B;int dp[N][N];
void solve(){
    cin>>A>>B;
    mst(dp,127);
    for(int i=0;i<=SZ(B);i++){
        dp[0][i]=i;
    }
    for(int i=0;i<=SZ(A);i++){
        dp[i][0]=i;
    }
    string AA="&"+A,BB="&"+B;
    for(int i=1;i<=SZ(A);i++){
        for(int j=1;j<=SZ(B);j++){
            if(AA[i]==BB[j]){
                dp[i][j]=dp[i-1][j-1];    
            }else{
                dp[i][j]=min(dp[i][j],
                    min(dp[i-1][j-1]+1,
                    min(dp[i-1][j]+1,dp[i][j-1]+1)));
            }
        }
    }
    cout<<dp[SZ(A)][SZ(B)]; }
}