算法基础之最短编辑距离

最短编辑距离

  • 核心思想 : 线性dp

    • 集合定义 : f[i][j]为操作方式的最小值

    • 集合计算 : 三种操作 取最小

      • ① 删除 : 将a[i]删掉 使ab相同 –> f[i-1][j] + 1 = f[i][j]
      • ② 增添 : 在a[i]后加上一个数 使ab相同 –> f[i][j-1] + 1 = f[i][j]
      • ③ 替换 : 将a[i] 换成 b[j] 使ab相同 若a[i] == b[j] 则不用操作
        • ​ 若!= 则 f[i-1][j-1] + 1 = f[i][j]
    • 在这里插入图片描述

      •   #include<iostream>
          #include<algorithm>
          #include<cstring>
          
          using namespace std;
          const int N = 1010;
          
          int n,m;
          char a[N],b[N];
          int f[N][N];
          
          int main()
          {
              cin>>n>>a+1>>m>>b+1;
              //初始化 因为求的是最小值 所以初始0的话结果会错
              //第一个是 a是空的 添加m次 和b相同
              //第二个是 a是非空的 删除n次 和b相同
              for(int i=1;i<=m;i++) f[0][i] = i;
              for(int i=1;i<=n;i++) f[i][0] = i;
              
              for(int i=1;i<=n;i++)
              {
                  for(int j=1;j<=m;j++)
                  {
                      //先取两个确定的式子的最小值
                      f[i][j] = min(f[i-1][j] +1 ,f[i][j-1] + 1);
                      if(a[i] == b[j]) 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);
                  }
              }
              
              cout<<f[n][m];
          }
        

    一点思考 : 为什么确定删掉a[i]就能使a[i-1] 和 b[j] 相等 ?

    ​ 因为在求a[i-1]时 已经从概念上使它和b[j]相等 (不等的话操作次数+1 然后就等了)

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

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

相关文章

基于ssm的航空票务推荐系统的设计与实现论文

摘 要 传统信息的管理大部分依赖于管理人员的手工登记与管理&#xff0c;然而&#xff0c;随着近些年信息技术的迅猛发展&#xff0c;让许多比较老套的信息管理模式进行了更新迭代&#xff0c;航班信息因为其管理内容繁杂&#xff0c;管理数量繁多导致手工进行处理不能满足广大…

基于Python的新闻爬取和推荐系统实践

基于Python的新闻爬取和推荐系统实践 项目概述数据集来源技术栈功能特点普通用户功能管理员功能需求 创新点 项目概述 在这个全功能的新闻爬取和推荐系统项目中&#xff0c;我们致力于构建一个高效、智能的平台&#xff0c;为用户提供个性化的新闻阅读体验。采用了Python语言&…

oracle执行不了update

oracle数据库select等其他语句执行正常&#xff0c;update语句执行后一直执行不完&#xff0c;原因是产生了记录锁。 &#xff08;1&#xff09;查询锁 SELECT a.sid, a.serial#,a.USERNAME,ao.OBJECT_NAME FROM v$locked_object lo, dba_objects ao, v$session a WHERE ao.o…

C语言易错知识点十(指针(the final))

❀❀❀ 文章由不准备秃的大伟原创 ❀❀❀ ♪♪♪ 若有转载&#xff0c;请联系博主哦~ ♪♪♪ ❤❤❤ 致力学好编程的宝藏博主&#xff0c;代码兴国&#xff01;❤❤❤ 许久不见&#xff0c;甚是想念&#xff0c;真的是时间时间&#xff0c;你慢些吧&#xff0c;不能再让头发变秃…

电子邮件地址填写指南:格式与常见问题解答

一个专业的电子邮件地址是一个你只用于工作目的的通信帐户。当你给收件人发送电子邮件时&#xff0c;这是他们最先看到的细节之一。无论你的职位或行业如何&#xff0c;拥有一个专业的电子邮件地址都可以提高你和所在公司的可信度。 在本文中我们解释了专业的电子邮件地址是什么…

PAT 乙级 1033 旧键盘打字

旧键盘上坏了几个键&#xff0c;于是在敲一段文字的时候&#xff0c;对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键&#xff0c;打出的结果文字会是怎样&#xff1f; 输入格式&#xff1a; 输入在 2 行中分别给出坏掉的那些键、以及应该输入的文字。其…

使用Vue3开发学生管理系统模板1

环境搭建 通过解压之前《Vue3开发后台管理系统模板》的代码&#xff0c;我们能够得到用户增删改查的页面&#xff0c;我们基于用户增删改查的页面做进一步的优化。 创建学生增删改查页面 第一步&#xff1a;复制用户增删改查页面&#xff0c;重命名为StudentCRUD.vue <…

java图书管理系统

主要模块&#xff1a; 为用户开通借书服务增加图书信息登记图书借出信息 技术栈&#xff1a; JSPServletTomcat9.0IDEAMysql 前台登录验证使用框架 数据库脚本包括登录用户名和密码已经写在了数据库脚本.sql 中 解压“需要的jar包”添加到项目的dependency中 运行效果&a…

构建基于小红书笔记详情API的内容生态

随着互联网的发展&#xff0c;内容生态的构建已经成为了许多企业和个人的重要任务。小红书作为一家以内容分享为主的社交平台&#xff0c;其API的开放为开发者提供了一种全新的方式来获取用户生成内容&#xff08;UGC&#xff09;。本文将介绍如何从无到有地构建基于小红书笔记…

告别HTTP,拥抱HTTPS!免费SSL证书领取指南

为什么选择HTTPS&#xff1f; HTTP和HTTPS之间的主要区别在于安全性。HTTP是一种不安全的协议&#xff0c;数据在传输过程中是明文的&#xff0c;容易受到中间人攻击。而HTTPS通过SSL&#xff08;Secure Sockets Layer&#xff09;或TLS&#xff08;Transport Layer Security&…

zabbix通过自动发现-配置监控项、触发器(小白教程)

自动发现配置参考链接&#xff08;不小白&#xff0c;不友好&#xff09; zabbix-get介绍 1配置 zabbix server&#xff1a;版本7&#xff08;不影响&#xff09;,IP地址&#xff1a;192.168.0.60zabbix agent&#xff1a;版本agent1&#xff08;不影响&#xff09;&#xff…

【Graylog】通过Pipelines在Graylog生成IP地理位置信息

序 在当今数字化时代&#xff0c;随着网络攻击的不断增加和全球化的用户活动&#xff0c;了解IP地址的地理位置信息变得越来越重要。对于网络安全和营销策略来说&#xff0c;掌握IP地址的地理信息可以带来许多好处。 接下里将介绍如何通过Graylog的Pipelines功能&#xff0c;…

arkts中@Watch监听的使用

概述 Watch用于监听状态变量的变化&#xff0c;当状态变量变化时&#xff0c;Watch的回调方法将被调用。Watch在ArkUI框架内部判断数值有无更新使用的是严格相等&#xff08;&#xff09;&#xff0c;遵循严格相等规范。当在严格相等为false的情况下&#xff0c;就会触发Watch的…

【数据结构——图】图的最短路径(头歌习题)【合集】

目录 第1关&#xff1a;单源最短路径完整代码 第2关&#xff1a;多源最短路径输入格式:输出格式:完整代码 第1关&#xff1a;单源最短路径 给一个n(1 ≤ n ≤ 2500) 个点 m(1 ≤ m ≤ 6200) 条边的无向图&#xff0c;求 s 到 t 的最短路。 输入格式: 第一行四个由空格隔开的整…

计算机视觉工程师就业前景如何

计算机视觉主要涵盖了图像处理、模式识别等多个领域&#xff0c;可以应用到很多行业中。随着人工智能技术的快速发展&#xff0c;计算机视觉作为其中的重要分支之一&#xff0c;其就业前景非常广阔。 为进一步贯彻落实中共中央印发《关于深化人才发展体制机制改革的意见》和国…

AIGC重塑基础设施,高密数据中心为何众望所归?

凯文凯利在《必然》中认为&#xff0c;科技在本质上有所偏好&#xff0c;使得它朝往某种特定方向。 毫无疑问&#xff0c;进入到数字经济时代&#xff0c;人工智能技术飞速发展与加速应用之际&#xff0c;这个特定方向逐渐明朗&#xff1a;即算力科技&#xff0c;算力已经成为…

驾驶人类未来:Apollo自动驾驶系统的影响力

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 ChatGPT体验地址 文章目录 前言1. 什么是自定义指令&#xff1f;2. Apollo中的自定义指令2.1 查询中的自定义指令2.2 变更操作中的自定义指令 3. 自定义指令的实现结论 文章目录 前言1. 什…

原型链补充

1.什么是原型对象 函数的独有属性,他用prototype来表示,可以在函数的prototype上挂载一些公用的属性和方法,供实例化对象来访问。 2.__proto__属性 这个属性每一个对象都有,实例化对象就是通过这个属性,来访问原型对象上的属性和方法的。 3.三者之间的关系 1.在构造函数的原型…

力扣算法-Day16

目录 454. 四数相加 II 383. 赎金信 454. 四数相加 II 给你四个整数数组 nums1、nums2、nums3 和 nums4 &#xff0c;数组长度都是 n &#xff0c;请你计算有多少个元组 (i, j, k, l) 能满足&#xff1a; 0 < i, j, k, l < nnums1[i] nums2[j] nums3[k] nums4[l] …

用linux中定时任务Crontab,向企业微信群通过机器人发送消息

1.使用yum命令安装Crontab&#xff1a;这个很关键&#xff0c;没有安装的话会提示命令not found yum install vixie-cron yum install crontabs 注&#xff1a;vixie-cron软件包是cron的主程序&#xff1b; crontabs软件包是用来安装、卸装、或列举用来驱动 cron 守护进程的表…