牛客题霸 -- HJ52 计算字符串的编辑距离

在这里插入图片描述
解题步骤:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

参考代码:

int main()
{
	string s1;
	string s2;
	while (cin >> s1 >> s2)
	{
		int m=s1.size();
		int n=s2.size();
		//增加空白字符,修正下标的映射关系
		s1=' '+s1;
		s2=' '+s2;
		//多卡一行,多开一列
		vector<vector<int>> dp(m+1,vector<int>(n+1));
		//初始化
		for(int i=0;i<=m;i++)
		{
			dp[i][0]=i;
		}
		for(int j=0;j<=n;j++)
		{
			dp[0][j]=j;
		}
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
			{
				//状态转移方程
				if(s1[i]==s2[j])
				{
					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;
				}
			}
		}
		cout<<dp[m][n]<<endl;
	}
	return 0;
}

你学会了吗???

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/107958.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

stable-diffusion-ui 下载和安装

简介 Stable Diffusion Web UI是一款基于Stable Diffusion基础应用的交互程序&#xff0c;它利用gradio模块搭建而成。这个模块除了具有txt2img、img2img等基本功能外&#xff0c;还包含许多模型融合改进、图片质量修复等附加升级。所有这些功能都可以通过易于使用的Web应用程…

C语言二、八、十六进制转换

二进制转八进制、十六进制 二进制转八进制&#xff1a; 三合一法&#xff1a; 从低位到高位&#xff0c;每 3 给二进制组成 1 位八进制数据&#xff0c;高位不够三位用 0 填补&#xff0c;将二进制转为对应的八进制数即可 二进制转十六进制&#xff1a; 四合一法&#xff1a;…

迁移学习 - 微调

什么是与训练和微调&#xff1f; 你需要搭建一个网络模型来完成一个特定的图像分类的任务。首先&#xff0c;你需要随机初始化参数&#xff0c;然后开始训练网络&#xff0c;不断调整参数&#xff0c;直到网络的损失越来越小。在训练的过程中&#xff0c;一开始初始化的参数会…

sql-50练习题0-5

sql练习题0-5题 前言数据库表结构介绍学生表课程表成绩表教师表 0-1 查询"01"课程比"02"课程成绩高的学生的信息及课程分数0-2查询"01"课程比"02"课程成绩小的学生的信息及课程分数0-3查询平均成绩大于等于60分的同学的学生编号和学生…

ETL工具Kettle

1 Kettle的基本概念 一个数据抽取过程&#xff0c;主要包括创建一个作业&#xff08;Job&#xff09;&#xff0c;每个作业由一个或多个作业项&#xff08;Job Entry&#xff09;和连接作业项的作业跳&#xff08;Job Hop&#xff09;组成。每个作业项可以是一个转换&#xff…

RGB-T Salient Object Detection via Fusing Multi-Level CNN Features

ADFC means ‘adjacent-depth feature combination’&#xff0c;MGF means ‘multi-branch group fusion’&#xff0c;JCSA means ‘joint channel-spatial attention’&#xff0c;JABMP means ‘joint attention guided bi-directional message passing’ 作者未提供代…

openpnp - src - 配置文件载入过程的初步分析

文章目录 openpnp - src - 配置文件载入过程的初步分析概述笔记自己编译用的git版本报错截图问题1 - 怎么在调试状态下, 定位到抛异常的第一现场?结合单步调试找到的现场, 来分析报错的原因openpnp配置文件读取的流程END openpnp - src - 配置文件载入过程的初步分析 概述 从…

LVS+keepalive高可用集群

keepalive简介 keepalive为LVS应用延伸的高可用服务。lvs的调度器无法做高可用。但keepalive不是为lvs专门集群服务的&#xff0c;也可以为其他的的代理服务器做高可用。 keepalive在lvs的高可用集群&#xff0c;主调度器和备调度器(可以有多个) 一主两备或一主一备。 VRRP: k…

[红蓝攻防]MDOG(全新UI重制版)为Xss跨站而生,数据共享,表单劫持,URL重定向

说明 功能Cookie窃取表单劫持(钓鱼账密)重定向流量劫持多平台数据推送钉钉数据推送 运行窗口 ./dist目录下已生成exe文件,双击打开 Cookie窃取 点击运行服务,复制以上的payload,payload怎么变形那么你可已去混淆 payload在页面执行 受害者访问存在xss漏洞的页面时受到攻击,…

python实验2 π的计算

π的计算 1. 圆周率的介绍2. BBP公式计算圆周率3. 蒙特卡洛方法计算π 1. 圆周率的介绍 圆周率π自古就是人们计算的问题&#xff0c;π到底是什么&#xff0c;圆的周长与直径的比值或者是面积与半径的平方之比&#xff0c;或者是使sinx0的最小正数x。所以每一种定义每一种理解…

NSSCTF web刷题记录3

文章目录 [护网杯 2018]easy_tornado[NSSRound#V Team]PYRCE方法一 cp命令方法二 tar命令 [CISCN 2019华东南]Web4[CISCN 2023 华北]ez_date[GWCTF 2019]你的名字[GKCTF 2020]ez三剑客-easynode [护网杯 2018]easy_tornado 打开题目&#xff0c;发现有三个链接&#xff0c;分别…

【Effective C++】

Effective C 文章目录 Effective C一、让自己习惯C条款01&#xff1a;视C为一个语言联邦条款02&#xff1a;尽量以const&#xff0c;enum&#xff0c;inline代替#define的使用条款03&#xff1a;尽可能使用const条款04&#xff1a;确定对象被使用前已先被初始化 二、构造/析构/…

Flutter笔记:完全基于Flutter绘图技术绘制一个精美的Dash图标(中)

Flutter笔记 完全基于Flutter绘图技术绘制一个精美的Dart语言吉祥物Dash&#xff08;中&#xff09; 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://…

C/C++晶晶赴约会 2020年12月电子学会青少年软件编程(C/C++)等级考试一级真题答案解析

目录 C/C晶晶赴约会 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C/C晶晶赴约会 2020年12月 C/C编程等级考试一级编程题 一、题目要求 1、编程实现 晶晶的朋友贝贝约晶晶下周一起去看展览&#xff0…

25.2 MySQL 运算符

1. 伪表 在MySQL中, DUAL是一个特殊的单行, 单列的虚拟表, 主要用于在SELECT语句中计算表达式或执行函数, 而不需要从实际的数据表中检索数据. 使用DUAL的原因主要有以下几点:* 1. 简化计算: 通过在SELECT语句中使用DUAL, 可以方便地计算表达式或执行函数, 而无需创建临时表或…

AJAX原理及介绍

文章目录 AJAX&#xff08;Asynchronous Javascript And Xml&#xff09;传统请求及缺点AJAX概述XMLHttpRequest对象AJAX GET请求AJAX GET请求的缓存问题AJAX POST请求基于JSON的数据交换基于XML的数据交换AJAX乱码问题AJAX的异步与同步AJAX代码封装AJAX实现省市联动AJAX跨域问…

磁盘的结构(磁道,扇区,盘面,柱面,物理地址)

目录 1.磁盘、磁道、扇区的概念1.磁盘2.磁道3.扇区 2.如何在磁盘中读/写数据3.盘面、柱面的概念4.磁盘的物理地址1.根据地址读取一个“块” 5.磁盘的分类1.活动头磁道2.固定头磁盘3.根据盘片是否可更换 1.磁盘、磁道、扇区的概念 1.磁盘 磁盘的表面由一些磁性物质组成&#xf…

打破尺寸记录!荷兰QuTech研发16量子点阵列新技术

承载16个量子点交叉条阵列的量子芯片&#xff0c;可无缝集成到棋盘图案&#xff08;图片来源&#xff1a;网络&#xff09; 由荷兰代尔夫特理工大学(TU Delft)和荷兰应用科学研究组织(TNO)组建的荷兰量子计算研究中心QuTech的研究人员开发了一种用相对较少的控制线来控制大量量…

双向链表的初步练习

&#x1d649;&#x1d65e;&#x1d658;&#x1d65a;!!&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦ &#x1f44f;&#x1f3fb;‧✧̣̥̇: Solitary-walk ⸝⋆ ━━━┓ - 个性标签 - &#xff1a;来于“云”的“羽球人”…

Redis进军磁盘存储

目录 1、对抗价格优势&#xff1a;纳入磁盘&#xff0c;降低成本&#xff1f; 2、Redis的野心&#xff1a;无敌是多么寂寞&#xff0c;所以我们要开新地图 3、开发者异议&#xff1a;他们正在偏离我们选择Redis的初衷 4、结语&#xff1a;性能为王&#xff0c;但绝不甘于只…