力扣1143. 最长公共子序列(动态规划)
Problem: 1143. 最长公共子序列
文章目录
- 题目描述
- 思路
- 复杂度
- Code
题目描述
思路
我们统一标记:str1[i]代表text1表示的字符数组,str2[j]代表text2表示的字符数组;LCS代表最长的公共子序列;(我们易得只有str1[i]和str2[j]均在LCS中时才能说明str1[i]和str2[j]是LCS的一部分)
1.状态定义:dp[i][j]代表str1[1~i]和str2[1 ~ j]的最长公共子序列(我们暂时认为索引是从 1 开始的,例如:d[2][4] 的含义就是:对于 “ac” 和 “babc” ,它们的LCS ⻓度是 2)
2.状态转移:2.1:初始状态初始化:我们初始化dp[0][j] = 0; dp[i][0] = 0,逻辑上说明,当str1或者str2其中为空时则LCS为0;
2.2:状态转移:若*str1[i] == str2[j]则dp[i][j] = dp[i - 1][j - 1] + 1;若str1[i] != str2[j]*则dp[i][j] == max(dp[i-1][j],dp[i][j-1])
补充:
当*str1[i] != str2[j]*实则有三种状态:str1[i] != LCS[i];str2[j] != LCS[j]; str1[i] != str2[i] != LCS[i];但是我们在状态转移方程中dp[i][j] == max(dp[i-1][j],dp[i][j-1]);
实际上dp[i][j] == max(dp[i-1][j],dp[i][j-1],dp[i - 1][j - 1]),但是回看dp[i][j]的定义我们易知dp[i - 1][j - 1]是一定小于dp[i-1][j]和dp[i][j-1],所以我们则直接求取**max(dp[i-1][j],dp[i][j-1])**即可
复杂度
时间复杂度:
O ( M × N ) O(M \times N) O(M×N);其中 M M M为text1的长度, N N N为text2的长度
空间复杂度:
O ( M × N ) O(M \times N) O(M×N)
Code
class Solution {
public:/*** Find the longest common subsequence* @param text1 Given string* @param text2 Given string* @return int*/int longestCommonSubsequence(string text1, string text2) {int len1 = text1.length();int len2 = text2.length();//DP arrayvector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));//for (int i = 1; i < len1 + 1; ++i) {for (int j = 1; j < len2 + 1; ++j) {if (text1.at(i - 1) == text2.at(j - 1)) {dp[i][j] = 1 + dp[i - 1][j - 1];} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[len1][len2];}
};
相关文章:

力扣1143. 最长公共子序列(动态规划)
Problem: 1143. 最长公共子序列 文章目录 题目描述思路复杂度Code 题目描述 思路 我们统一标记:str1[i]代表text1表示的字符数组,str2[j]代表text2表示的字符数组;LCS代表最长的公共子序列;(我们易得只有str1[i]和str…...

如何使用群晖NAS中FTP服务开启与使用固定地址远程上传下载本地文件?
文章目录 1. 群晖安装Cpolar2. 创建FTP公网地址3. 开启群晖FTP服务4. 群晖FTP远程连接5. 固定FTP公网地址6. 固定FTP地址连接 本文主要介绍如何在群晖NAS中开启FTP服务并结合cpolar内网穿透工具,实现使用固定公网地址远程访问群晖FTP服务实现文件上传下载。 Cpolar内…...

C语言文件知识点
一.解释一些问题 1.标准输入文件(sdtin),通常对应终端的键盘。 2.标准输出文件(stdout)和标准错误输出文件(stderr),这两个文件 都对应终端的屏幕。 (解释:…...

C语言:数组指针 函数指针
C语言:数组指针 & 函数指针 数组指针数组名 数组访问二维数组 函数指针函数指针使用回调函数 typedef关键字 数组指针 数组本质上也是一个变量,那么数组也有自己的地址,指向整个数组的指针,就叫做数组指针。 我先为大家展示…...

全面介绍HTML的语法!轻松写出网页
文章目录 heading(标题)paragraph(段落)link(超链接)imagemap(映射)table(表格)list(列表)layout(分块)form(表单)更多输入:datalistautocompleteautofocusmultiplenovalidatepatternplaceholderrequired head(首部)titlebaselinkstylemetascriptnoscript iframe HTMLÿ…...

数学建模【相关性模型】
一、相关性模型简介 相关性模型并不是指一个具体的模型,而是一类模型,这一类模型用来判断变量之间是否具有相关性。一般来说,分析两个变量之间是否具有相关性,我们根据数据服从的分布和数据所具有的特点选择使用pearsonÿ…...

「优选算法刷题」:字母异位词分组
一、题目 给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs ["eat", "tea", "tan", "ate", "na…...

【教程】 iOS混淆加固原理篇
目录 摘要 引言 正文 1. 加固的缘由 2. 编译过程 3. 加固类型 1) 字符串混淆 2) 类名、方法名混淆 3) 程序结构混淆加密 4) 反调试、反注入等一些主动保护策略 4. 逆向工具 5. OLLVM 6. IPA guard 7. 代码虚拟化 总结 摘要 本文介绍了iOS应用程序混淆加固的缘由…...

《银幕上的编码传奇:计算机科学与科技精神的光影盛宴》
目录 1.在电影的世界里,计算机科学不仅是一门严谨的学科,更是一种富有戏剧张力和人文思考的艺术载体。 2.电影作为现代文化的重要载体,常常以其丰富的想象力和视觉表现力来探讨计算机科学和技术的各种前沿主题。 3.电影中的程序员角色往往…...

linux提权之sudo风暴
🍬 博主介绍👨🎓 博主介绍:大家好,我是 hacker-routing ,很高兴认识大家~ ✨主攻领域:【渗透领域】【应急响应】 【Java】 【VulnHub靶场复现】【面试分析】 🎉点赞➕评论➕收藏 …...

数据结构之:跳表
跳表(Skip List)是一种概率性数据结构,它通过在普通有序链表的基础上增加多级索引层来实现快速的查找、插入和删除操作。跳表的效率可以与平衡树相媲美,其操作的时间复杂度也是O(log n),但跳表的结构更简单,…...

matlab 线性四分之一车体模型
1、内容简介 略 57-可以交流、咨询、答疑 路面采用公式积分来获得,计算了车体位移、非悬架位移、动载荷等参数 2、内容说明 略 3、仿真分析 略 线性四分之一车体模型_哔哩哔哩_bilibili 4、参考论文 略...

LeetCode第二题: 两数相加
文章目录 题目描述示例 解题思路 - 迭代法Go语言实现 - 迭代法算法分析 解题思路 - 模拟法Go语言实现 - 模拟法算法分析 解题思路 - 优化模拟法主要方法其他方法的考虑 题目描述 给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方…...

web组态插件
插件演示地址:http://www.byzt.net 关于组态软件,首先要从组态的概念开始说起。 什么是组态 组态(Configure)的概念来自于20世纪70年代中期出现的第一代集散控制系统(Distributed Control System)…...

Android14 InputManager-InputManagerService环境的构造
IMS分为Java层与Native层两个部分,其启动过程是从Java部分的初始化开始,进而完成Native部分的初始化。 □创建新的IMS对象。 □调用IMS对象的start()函数完成启动 同其他系统服务一样,IMS在SystemServer中的ServerT…...

搜维尔科技:【周刊】适用于虚拟现实VR中的OptiTrack
适用于 VR 的 OptiTrack 我们通过优化对虚拟现实跟踪最重要的性能指标,打造世界上最准确、最易于使用的广域 VR 跟踪器。其结果是为任何头戴式显示器 (HMD) 或洞穴自动沉浸式环境提供超低延迟、极其流畅的跟踪。 OptiTrack 主动式 OptiTrack 世界领先的跟踪精度和…...

matlab倒立摆小车LQR控制动画
1、内容简介 略 54-可以交流、咨询、答疑 2、内容说明 略 摆杆长度为 L,质量为 m 的单级倒立摆(摆杆的质心在杆的中心处),小车的质量为 M。在水平方向施加控制力 u,相对参考系产生位移为 y。为了简化问题并且保其实质不变,忽…...

【C++】类和对象(2)
目录 1. 初始化列表 2.explicit关键字 3. Static成员 3. 友元 3.1友元函数 3.2友元类 4. 内部类 5.匿名对象 1. 初始化列表 在创建对象时,编译器通过调用构造函数,给对象中各个成员变量一个合适的初始值,但是这个过程并不能称为对对…...

用Python实现创建十二星座数据分析图表
下面小编提供的代码中,您已经将pie.render()注释掉,并使用了pie.render_to_file(十二星座.svg)来将饼状图渲染到一个名为十二星座.svg的文件中。这是一个正确的做法,如果您想在文件中保存图表而不是在浏览器中显示它。 成功创建图表…...

备战蓝桥杯————递归反转单链表的一部分
递归反转单链表已经明白了,递归反转单链表的一部分你知道怎么做吗? 一、反转链表Ⅱ 题目描述 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left < right 。请你反转从位置 left 到位置 right 的链表节点,返回 反…...

rabbitmq知识梳理
一.WorkQueues模型 Work queues,任务模型。简单来说就是让多个消费者绑定到一个队列,共同消费队列中的消息。 当消息处理比较耗时的时候,可能生产消息的速度会远远大于消息的消费速度。长此以往,消息就会堆积越来越多,…...

【数据结构与算法】动态规划法解题20240227
动态规划法 一、什么是动态规划二、动态规划的解题步骤三、509. 斐波那契数1、动规五部曲: 四、70. 爬楼梯1、动规五部曲: 五、746. 使用最小花费爬楼梯1、动规五部曲: 一、什么是动态规划 动态规划,英文:Dynamic Pro…...

备战蓝桥杯—— 双指针技巧巧答链表2
对于单链表相关的问题,双指针技巧是一种非常广泛且有效的解决方法。以下是一些常见问题以及使用双指针技巧解决: 合并两个有序链表: 使用两个指针分别指向两个链表的头部,逐一比较节点的值,将较小的节点链接到结果链表…...

半监督节点分类-graph learning
半监督节点分类相当于在一个图当中,用一部分节点的类别上已知的,有另外一部分节点的类别是未知的,目标是使用有标签的节点来推断没有标签的节点 注意 半监督节点分类属于直推式学习,直推式学习相当于出现新节点后,需要…...

软件文档-运维-开发-管理-资质-评审-招投标-验收
开发文档:这类文档主要用于记录软件的开发过程和细节,包括: 《功能要求》:描述了软件应具备的功能,是软件开发的基础。《投标方案》:向潜在的客户或招标方展示公司的技术和项目实施能力。《需求分析》&…...

猫头虎分享已解决Bug || Vue中的TypeError: Cannot read property ‘name‘ of undefined 错误
博主猫头虎的技术世界 🌟 欢迎来到猫头虎的博客 — 探索技术的无限可能! 专栏链接: 🔗 精选专栏: 《面试题大全》 — 面试准备的宝典!《IDEA开发秘籍》 — 提升你的IDEA技能!《100天精通鸿蒙》 …...

技术应用:使用Spring Boot、MyBatis Plus和Dynamic DataSource实现多数据源
引言 在现代的软件开发中,许多应用程序需要同时访问多个数据库。例如,一个电子商务平台可能需要访问多个数据库来存储用户信息、产品信息和订单信息等。在这种情况下,使用多数据源是一种常见的解决方案,它允许我们在一个应用程序…...

C# Onnx 使用onnxruntime部署实时视频帧插值
目录 介绍 效果 模型信息 项目 代码 下载 C# Onnx 使用onnxruntime部署实时视频帧插值 介绍 github地址:https://github.com/google-research/frame-interpolation FILM: Frame Interpolation for Large Motion, In ECCV 2022. The official Tensorflow 2…...

编程笔记 Golang基础 016 数据类型:数字类型
编程笔记 Golang基础 016 数据类型:数字类型 1. 整数类型(Integer Types)a) 固定长度整数:b) 变长整数: 2. 浮点数类型(Floating-Point Types)3. 复数类型(Complex Number Types&…...

一周学会Django5 Python Web开发-会话管理(CookiesSession)
锋哥原创的Python Web开发 Django5视频教程: 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计26条视频,包括:2024版 Django5 Python we…...