首页 > 其他 > 详细

P2758 编辑距离【dp】

时间:2020-11-07 19:44:57      阅读:28      评论:0      收藏:0      [点我收藏+]

题目描述

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

1、删除一个字符;

2、插入一个字符;

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

!皆为小写字母!

输入格式

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

输出格式

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

输入输出样例

输入 #1
sfdqxbw
gfdgw
输出 #1
4

题解:
  用f[i][j]表示a串中前i个字母和b串中前j个字母的最小操作数
  有变和不变两种情况
  不变:a[i] = b[j]时,f[i][j] = f[i - 1][j - 1];
  变:增加:f[i][j] = f[i][j - 1] + 1
    减少:f[i][j] = f[i - 1][j] + 1
    改变:f[i][j] = f[i - 1][j - 1] + 1

CODE
技术分享图片
 1 #include <bits/stdc++.h>
 2 #define dbug(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 #define pi acos(-1.0)
 5  
 6 using namespace std;
 7 typedef long long LL;
 8  
 9 const int inf = 0x3f3f3f3f;
10  
11 template<class T>inline void read(T &res)
12 {
13    char c;T flag=1;
14    while((c=getchar())<0||c>9)if(c==-)flag=-1;res=c-0;
15    while((c=getchar())>=0&&c<=9)res=res*10+c-0;res*=flag;
16 }
17 
18 const int maxn = 2e5 + 7;
19 
20 string a, b;
21 int f[2007][2007];
22 
23 int main()
24 {
25     cin >> a;
26     cin >> b;
27     int lena = a.size();
28     int lenb = b.size();
29     for ( int i = 0; i <= lena; ++i ) {
30         f[i][0] = i;
31     }
32     for ( int i = 0; i <= lenb; ++i ) {
33         f[0][i] = i;
34     }
35     for ( int i = 1; i <= lena; ++i ) {
36         for ( int j = 1; j <= lenb; ++j ) {
37             if(a[i - 1] == b[j - 1]) {
38                 f[i][j] = f[i - 1][j - 1];
39             }
40             else {
41                 f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
42             }
43         }
44     }
45     cout << f[lena][lenb] << endl;
46     return 0;
47 }
View Code

 


  

P2758 编辑距离【dp】

原文:https://www.cnblogs.com/orangeko/p/13941802.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!