首页 > 其他分享 >线性DP——伴随插入、删除操作

线性DP——伴随插入、删除操作

时间:2024-03-20 22:14:44浏览次数:30  
标签:字符 删除 int 插入 字符串 线性 操作 DP

编辑距离

题目描述

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

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

\(A, B\) 均只包含小写字母。

输入格式

第一行为字符串 \(A\);第二行为字符串 \(B\);字符串 \(A, B\) 的长度均小于 \(2000\)。

输出格式

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

样例 #1

样例输入 #1

sfdqxbw
gfdgw

样例输出 #1

4

提示

对于 \(100 \%\) 的数据,\(1 \le |A|, |B| \le 2000\)。

最近遇到了很多类似这样的题,所以把这些题整理在一起。刚开始我以为这个黄题,可以使用贪心模拟来做,但是贪心是错的,我们来DP考虑

对于修改操作而言,非常好做,因为它不会改变字符串的长度

对于插入和删除操作,插入会增加长度,删除操作会减少长度,对于这样的DP,我们会设定\(dp[i][j]表示将A串前i个位置变成B串前j个位置的最少编辑距离是多少?\)刚开始的想法是,如果我们在A串第i个位置插入字符串之后,A串的i+1个位置就变化了,这怎么DP呢?

做这种题的宗旨是无论插入、删除操作,我们不要让它影响原来的位置关系

对于这道题而言,假设\(a[i]==b[j],那么f[i][j]=f[i-1][j-1],如果a[i]!=b[j]呢,我们需要进行插入和删除操作,如果我们进行插入操作,那么b[j]就要和插入的字符匹配,a[i]和b[j-1]进行匹配,f[i][j]=f[i][j-1]+1,如果我们进行的是删除操作呢,b[j]和a[i-1]就匹配好了,所以f[i][j]=f[i-1][j]+1,如果是修改操作的话,就更简单了,f[i][j]=f[i-1][j-1]+1,这个题就做完了\)

点击查看代码
#include<bits/stdc++.h>
using namespace std;
char s[2005],t[2005];
int f[2005][2005]; 
int main(){
	scanf("%s%s",s+1,t+1);
	int n=strlen(s+1);
	int m=strlen(t+1);
	memset(f,0x3f,sizeof f);
	f[0][0]=0;//边界,假设只有一个字符 
	for(int i=1;i<=n;i++)
		f[i][0]=i;// 需要进行i次删除操作
	for(int i=1;i<=m;i++)
		f[0][i]=i;// 需要进行i次添加操作 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(s[i]==t[j]) f[i][j]=f[i-1][j-1];
			else{
				f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
				f[i][j]=min(f[i][j],f[i-1][j-1]+1);
			}
		}
	cout<<f[n][m]<<endl;
	return 0;
}

标签:字符,删除,int,插入,字符串,线性,操作,DP
From: https://www.cnblogs.com/sdfzls/p/18086189

相关文章

  • 从时间复杂度的角度出发,list和vector之间查找,插入,删除等数据操作的区别
    list和vector是STL(标准模板库)中常用的两种序列容器,它们各自在不同类型的操作上有着不同的优势。下面是list和vector在不同操作上的擅长之处:list的擅长操作插入和删除操作:list是一个双向链表,插入和删除元素时只需要调整相邻节点的指针,因此在中间或任意位置插入或删除元素时效率很......
  • 如何理解UDP 和 TCP? 区别? 应用场景?
    一、UDPUDP(UserDatagramProtocol),用户数据包协议,是一个简单的面向数据报的通信协议,即对应用层交下来的报文,不合并,不拆分,只是在其上面加上首部后就交给了下面的网络层也就是说无论应用层交给UDP多长的报文,它统统发送,一次发送一个报文而对接收方,接到后直接去除首部,交给上面的应......
  • 11--插入排序
    算法描述:从当前位置开始,从后往前找比当前数字小的,插入到这个小的数字的后面,在找的过程中,如果发现一个比当前数字大,同时将这个数字往后挪动,其中从后往前是重点。插入排序的时间复杂度是,特别地,若完全有序则时间复杂度为空间复杂度为,并且它是稳定的。插入排序的特点:越有序越快......
  • 1312. 让字符串成为回文串的最少插入次数c
    intmin;voiddfs(char*s,inthead,inttail,intcount){if(head>=tail){if(count<min)min=count;return;}if(s[head]==s[tail]){dfs(s,head+1,tail-1,count);}else{dfs(s,head+1,tail,count+1);......
  • matlab实现线性回归机器学习
    一、要求1.编程实现LinearRegression模型,计算线性回归损失的函数,求解实际问题2.编程实现梯度下降算法(BGD、SGD、minibatch-GD),比较学习率α对结果影响3.使用LinearRegression的标准方程法求解最优解二、算法目标函数:成本函数:线性回归的目的是使得成本函数值最小求解......
  • Ubuntu E: 无法获得锁 /var/lib/dpkg/lock-frontend问题解决
    问题描述ubuntu18.04版本在更新出现:E:无法获得锁/var/lib/dpkg/lock-frontend-open(11:资源暂时不可用)即这个错误表明Ubuntu系统在尝试使用APT(高级包装工具)时无法获取一个锁文件。锁文件用于防止多个进程同时修改系统软件包数据库,以防止数据库损坏。错误信息中的“......
  • JAVA线程池ScheduledThreadPool实践教程
    ScheduledThreadPool用于在给定的延迟之后,或者定期执行任务。以下是如何在Java中实践使用ScheduledThreadPool的步骤:步骤1:创建ScheduledThreadPool首先,使用Executors的newScheduledThreadPool方法来创建一个ScheduledThreadPool。参数是你想要在池中保持的线程数量。i......
  • 技术支持Tektronix泰克DPO5104B数字示波器1GHz
    泰克DPO5104B数字示波器Bandwidth:1GHz4频道纪录长度:125米SampleRate:10/5GS/s(2/4ch)最多250兆跳记录长度,多视图变焦器。最大波形捕获率带310000帧的快速帧分段内存采集模式每秒捕获率标准的无源电压探针,其电容性小于4pp装载和500兆赫或1千兆赫模拟带宽......
  • 机器学习-线性代数
    二维空间-Singular平行的线是lineardependence的,singular的,相交的线是Non-singular的,交点就是二元方程解 在机器学习的计算过程中,等式右边的常数全部转化为0,确保每条线都经过(0,0)三维空间-singular平面相交于一条线或者重叠,则为singular线性相关有唯一解的方程组,是sing......
  • C++ Qt开发:QUdpSocket实现组播通信
    Qt是一个跨平台C++图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本章将重点介绍如何运用QUdpSocket组件实现基于UDP的组播通信。组播是一种一对多的通信方式,允许一个发送者将数......