博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷——P2758 编辑距离
阅读量:5849 次
发布时间:2019-06-19

本文共 1137 字,大约阅读时间需要 3 分钟。

P2758 编辑距离

题目描述

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

1、删除一个字符;

2、插入一个字符;

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

!皆为小写字母!

输入输出格式

输入格式:

 

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 
sfdqxbwgfdgw
输出样例#1: 
4

 

 

dp

我们用f[i][j]表示a字符串匹配到第i位,b字符串中匹配到第j位的最少的操作次数

如果当前的a字符串的位上的数与b上的数相等,那么最少的操作数就还是上面的

反之,如果不相等,那么我们肯定会执行删除一个字符;插入一个字符;将一个字符改为另一个字符;中的任意一个,这个时候我们就要去个最小值了,所以操作数+1

#include
#include
#include
#include
#define N 2100using namespace std;char a[N],b[N];int l1,l2,f[N][N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}int main(){ cin>>a+1>>b+1; l1=strlen(a+1),l2=strlen(b+1); for(int i=1;i<=l1;i++) f[i][0]=i; for(int i=1;i<=l2;i++) f[0][i]=i; for(int i=1;i<=l1;i++) for(int j=1;j<=l2;j++) if(a[i]==b[j]) f[i][j]=f[i-1][j-1]; else f[i][j]=min(f[i][j-1],min(f[i-1][j],f[i-1][j-1]))+1; printf("%d",f[l1][l2]); return 0;}

 

转载于:https://www.cnblogs.com/z360/p/7896207.html

你可能感兴趣的文章
为什么日本德国没有一流互联网企业?
查看>>
Java编程思想学习笔记——字符串
查看>>
项目开发-ASP.NET项目开发中的异常处理
查看>>
PL/SQL --> DML 触发器
查看>>
PHP设计模式学习笔记: 策略模式
查看>>
利用P2P终结者实现机顶盒限速
查看>>
python笔记(基础进阶1.8-1.9)
查看>>
Html5 web sql database
查看>>
Centos6.4制作Tengine的rpm包
查看>>
Jenkins进阶系列之——11详解Jenkins节点配置
查看>>
xshell远程连接centos7 rz/sz命名配置
查看>>
第一次来,因为一个CSS问题而来
查看>>
DAYDREAM和VIVE平台的框架API
查看>>
我和学员那些事
查看>>
DNS基本介绍及应用软件bind9编译安装
查看>>
禁止指定user_agent
查看>>
新手必须掌握的Linux命令
查看>>
Shell ⑦
查看>>
sso实现Cookie共享
查看>>
数据库工作于独立主机的lamp平台安装实现
查看>>