题面

题目描述

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

1、删除一个字符；

2、插入一个字符；

3、将一个字符改为另一个字符；

皆为小写字母

输入格式：

第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。

输出格式：

只有一个正整数，为最少字符操作次数。

Input

sfdqxbw

gfdgw

Output

4

题解

一道DP裸体

先设一下状态

设f[i][j]表示串S1前i个字符到串S2前j个字符的编辑距离

看一看每一个f[i][j]可以怎么得到：

如果当前有S1[i]=S2[j]那么f[i][j]=f[i-1][j-1]，直接由前面的状态就可以得到

否则：

1. 可以由i-1和j-1的匹配情况加上一次修改操作
2. 可以由i-1和j 的匹配情况加上一次删除操作
3. 可以由i 和j-1的匹配情况加上一次添加操作

所以状态转移方程就可以得出来了

后面就不用写了，直接看代码吧

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;string s1,s2;//初始字符串 int l1,l2;int f[5000][5000];int main(){ cin>>s1>>s2; l1=s1.length(); l2=s2.length(); memset(f,127,sizeof(f)); //f[i][j]表示把 s1前i位变为 s2的前j位的 最短编辑距离 for(int i=0;i<=l2;++i) f[0][i]=i; for(int i=0;i<=l1;++i) f[i][0]=i; for(int i=1;i<=l1;++i) { for(int j=1;j<=l2;++j) { if(s1[i-1]==s2[j-1]) 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);//上一位的基础上加"替换" f[i][j]=min(f[i][j],f[i][j-1]+1);//上一个的基础上加"添加" f[i][j]=min(f[i][j],f[i-1][j]+1);//上一位的基础上加"删除" } } cout<
          
           <