P2758 编辑距离

· · 题解

题目跳转

题目大意

用最少的字符操作次数，将字符串 A 转换为字符串 B。字符操作为：

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

    样例解析

    1. 将A[0] ('s')改为'g'

    2. 将A[3] ('q')删去

    3. 将A[3]（原A[4]） ('x')删去

    4. 将A[3]（原A[5]） ('b')改为'g'

    代码思路

    本题很明显用的是DP

    1. 赋值

    将dp数组的值赋值到最大

    2. 特殊赋值

    对关于字符串a的dp数组的特殊值进行赋值

    字符串a的前i个字符变为字符串b的前0个字符的最短编辑距离为i（全部都删除）

对关于字符串b的dp数组的特殊值进行赋值

字符串a的前0个字符变为字符串b的前i个字符的最短编辑距离为i（全部都增加与字符串b相同的字符）

3.状态转移

转移有三种(若两者相同，就不用换了):

  1. dp[i-1][j]->dp[i][j],插入即可,即dp[i][j]=dp[i-1][j]+1;
  2. dp[i][j-1]->dp[i][j],删除即可,即dp[i][j]=dp[i][j-1]+1;
  3. dp[i-1][j-1]->dp[i][j],要把sa[i-1]换成sb[j-1],即dp[i][j]=dp[i-1][j-1]+1。

合到一起就变成dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1

参考代码

/*请勿copy*/
#include<bits/stdc++.h>//万能头
#define int long long//可加可不加
using namespace std;//用cin,cout必写
const int maxn=2e3+1;//字符串最大长度（记得要多加一点）
string sa,sb;//定义字符串
int alen,blen;//记录字符串长度
int dp[maxn][maxn];//dp[i][j]代表字符串a的前i个字符变为字符串b的前j个字符的最短编辑距离
signed main(){//主程序
    cin>>sa>>sb;//输入
    alen=sa.size();//记录字符串a的长度
    blen=sb.size();//记录字符串b的长度
    memset(dp,0x3f,sizeof dp);//初始化，将dp数组的值赋值到最大
    //对关于字符串a的dp数组的特殊值进行赋值
    for(int i=0;i<=alen;i++){//注意字符串首位是从下标0开始
        dp[i][0]=i;//字符串a的前i个字符变为字符串b的前0个字符的最短编辑距离为i（全部都删除）
    }
    //对关于字符串b的dp数组的特殊值进行赋值
    for(int i=0;i<=blen;i++){//同上
        dp[0][i]=i;//字符串a的前0个字符变为字符串b的前i个字符的最短编辑距离为i（全部都增加与字符串b相同的字符）
    }
    for(int i=1;i<=alen;i++){//同上（i=0时已经处理过）
        for(int j=1;j<=blen;j++){//同上（j=0时也已经处理过）
            if(sa[i-1]==sb[j-1]) dp[i][j]=dp[i-1][j-1];//若两者相同，就不用换了
            else dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;//转移有三种: 1.dp[i-1][j]->dp[i][j],插入即可,即dp[i][j]=dp[i-1][j]+1; 2.dp[i][j-1]->dp[i][j],删除即可,即dp[i][j]=dp[i][j-1]+1; 3.dp[i-1][j-1]->dp[i][j],要把sa[i-1]换成sb[j-1],即dp[i][j]=dp[i-1][j-1]+1。 合到一起就变成dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1
        }
    }
    cout<<dp[alen][blen];//输出整个字符串的最短编辑距离
    return 0;//结束程序
}