最长子序列问题(LCS)--动态规划解法
题目描述:
如果Z既是X的子序列,又是Y的子序列,则称Z为X和Y的公共子序列。
如果给定X、Y,求出Y及其长度。
示例:
输入
ABCPDSFJGODIHJOFDIUSHGD
OSDIHGKODGHBLKSJBHKAGHI
输出
SDIHODSHG
9
分析:
c[i][j]表示X从0到i与Y从0到j之间公共子序列的长度。

代码 :
//最长子序列问题,不是最长字串问题
#include<iostream>
#include<stack>
using namespace std;const int N = 1000;
int dp[N][N] = { 0 };
int path[N][N];
int main()
{string a, b;cin >> a;cin >> b;int lena = a.size();int lenb = b.size();for (int i = 0; i <lena-1; i++){for (int j = 0; j <lenb-1; j++){if (a[i] == b[j]){dp[i+1][j+1] = dp[i][j] + 1;path[i + 1][j + 1] = 1;}else if (dp[i][j + 1] >= dp[i + 1][j]){dp[i + 1][j + 1] = dp[i][j + 1];path[i + 1][j + 1] = 2;}else{dp[i + 1][j + 1] = dp[i+1][j];path[i + 1][j + 1] = 3;}}}cout << "dp数组为:" << endl;for (int i = 0; i < lena; i++){for (int j = 0; j < lenb; j++){cout << dp[i][j] << ' ';}cout << endl;}cout << "最长子序列数为:" << dp[lena - 1][lenb - 1] << endl;//存放最长子序列stack<char>same;for (int i = lena - 1, j = lenb - 1; i >= 0 && j >= 0;){if (path[i][j] == 1){i--;j--;same.push(a[i]);}else if (path[i][j] == 2){i--;}else{j--;}}cout << "最长子序列为";while (!same.empty()){cout << same.top();same.pop();}cout << endl;system("pause");return 0;}
相关文章:
最长子序列问题(LCS)--动态规划解法
题目描述: 如果Z既是X的子序列,又是Y的子序列,则称Z为X和Y的公共子序列。 如果给定X、Y,求出Y及其长度。 示例: 输入 ABCPDSFJGODIHJOFDIUSHGD OSDIHGKODGHBLKSJBHKAGHI 输出 SDIHODSHG 9 分析: c…...
实时流式计算 kafkaStream
文章目录 实时流式计算Kafka StreamKafka Streams 的关键概念KStreamKafka Stream入门案例编写SpringBoot 集成 Kafka Stream 实时流式计算 一般流式计算会与批量计算相比较 流式计算就相当于上图的右侧扶梯,是可以源源不断的产生数据,源源不断的接收数…...
西南科技大学模拟电子技术实验七(集成运算放大器的非线性应用)预习报告
一、计算/设计过程 说明:本实验是验证性实验,计算预测验证结果。是设计性实验一定要从系统指标计算出元件参数过程,越详细越好。用公式输入法完成相关公式内容,不得贴手写图片。(注意:从抽象公式直接得出结果,不得分,页数可根据内容调整) 预习计算内容根据运放的非线…...
Ubuntu与Windows通讯传输文件(FTP服务器版)(没用的方法,无法施行)
本文介绍再Windows主机上建立FTP服务器,并且在Ubuntu虚拟机上面访问Windows上FTP服务器的方法 只要按照上图配置就可以了 第二部:打开IIS管理控制台 右击网站,新建FTP站点。需要注意的一点是在填写IP地址的时候,只需要填写Window…...
2024年AI视频识别技术的6大发展趋势预测
随着人工智能技术的快速发展,AI视频识别技术也将会得到进一步的发展和应用。2023年已经进入尾声,2024年即将来临,那么AI视频识别技术又将迎来怎样的发展趋势?本文将对2023年的AI视频技术做一个简单的盘点并对2024年的发展趋势进行…...
一篇文章了解JDK的前世今生
我们每天都在开发Java,每天都在使用JDK,那么我们了解JDK的发展史吗,这篇文章将带你深入了解JDK的发展史。 JDK(Java Development Kit)是Java开发者工具包,是用于编写Java程序和运行Java程序的软件开发工具集。自从1995年Java语言首次发布以来,JDK已经经历了数十年的发展…...
Redisson出现问题总结
org.redisson.client.RedisAuthRequiredException: NOAUTH Authentication required… channel: 出现此问题的原因为没有redis权限。解决方案在setAddress()后面加上setPassword()方法。 config.useSingleServer().setAddress("redis://localhost:6379").setPasswo…...
领域驱动架构(DDD)建模
一、背景 常见的软件开发方式是拿到产品需求后,直接考虑数据库中表应该如何设计,这种方式已经将设计与业务需求脱节,而更多的是直接考虑应该如何实现了,这有点本末倒置。而DDD是从领域(问题域)为出发点进行的设计方法。 领域驱动…...
PostgreSQL从小白到高手教程 - 第38讲:数据库备份
PostgreSQL从小白到专家,是从入门逐渐能力提升的一个系列教程,内容包括对PG基础的认知、包括安装使用、包括角色权限、包括维护管理、、等内容,希望对热爱PG、学习PG的同学们有帮助,欢迎持续关注CUUG PG技术大讲堂。 第38讲&#…...
OpenGL ES eglCreatePbufferSurface() 和 eglCreateWindowSurface() 的对比和使用
一、介绍 相同点: eglCreatePbufferSurface 和 eglCreateWindowSurface 都是 OpenGL ES 中用于创建不同类型的EGL表面的函数,以便在OpenGL ES中进行渲染。 不同点: 选择使用哪种表面类型取决于你的需求。如果你只是需要在内存中进行离屏渲…...
python之马尔科夫链(Markov Chain)
马尔可夫链(Markov Chain)是一种随机过程,具有“马尔可夫性质”,即在给定当前状态的条件下,未来状态的概率分布仅依赖于当前状态,而与过去状态无关。马尔可夫链在很多领域都有广泛的应用,包括蒙…...
数据库管理-第123期 Oracle相关两个参数(202301205)
数据库管理-第123期 Oracle相关两个参数(202301205) 最近在群聊中看到俩和Oracle数据库相关的俩参数,一个是Oracle数据库本身的,一个是来自于Weblogic的,挺有趣的,本期研究一下。(本期涉及参数…...
掌握vue中国际化使用及配置
文章目录 🍁i18n组件安装🍁项目中配置 vue-i18n🍁编写语言包🍁国际化的使用 随着互联网的普及和全球化的发展,开发国际化的应用程序已经成为一种趋势。因此,将 VUE 应用程序国际化是非常有必要的。 以下是…...
Ubuntu编译文件安装SNMP服务
net-snmp源码下载 http://www.net-snmp.org/download.html 编译步骤 指定参数编译 ./configure --prefix/root/snmpd --with-default-snmp-version"2" --with-logfile"/var/log/snmpd.log" --with-persistent-directory"/var/net-snmp" --wi…...
3D Web可视化平台助力Aras开发PLM系统:提供数据访问、可视化和发布功能
HOOPS中文网慧都科技是HOOPS全套产品中国地区指定授权经销商,提供3D软件开发工具HOOPS售卖、试用、中文试用指导服务、中文技术支持。http://techsoft3d.evget.com/ Aras是一个面向数字化工业应用的开放性平台,帮助世界领先的复杂互联产品制造商转变其产…...
Graphpad Prism10.1.0 安装教程 (含Win/Mac版)
GraphPad Prism GraphPad Prism是一款非常专业强大的科研医学生物数据处理绘图软件,它可以将科学图形、综合曲线拟合(非线性回归)、可理解的统计数据、数据组织结合在一起,除了最基本的数据统计分析外,还能自动生成统…...
【动态规划】路径问题_不同路径_C++
题目链接:leetcode不同路径 目录 题目解析: 算法原理 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 编写代码 题目解析: 题目让我们求总共有多少条不同的路径可到达右下角; 由题可得: 机器人位于…...
Python并发-线程和进程
一、线程和进程对应的问题 **1.进程:**CPU密集型也叫计算密集型,指的是系统的硬盘、内存性能相对CPU要好很多,此时,系统运作大部分的状况是CPU Loading 100%,CPU要读/写I/O(硬盘/内存),I/O在很短的时间就可…...
微信小程序适配方案:rpx(responsive pixel响应式像素单位)
小程序适配单位:rpx 规定任何屏幕下宽度为750rpx 小程序会根据屏幕的宽度自动计算rpx值的大小 Iphone6下:1rpx 1物理像素 0.5css 小程序编译后,rpx会做一次px换算,换算是以375个物理像素为基准,也就是在一个宽度…...
vue2 echarts饼状图,柱状图,折线图,简单封装以及使用
vue2 echarts饼状图,柱状图,折线图,简单封装以及使用 1. 直接上代码(复制可直接用,请根据自己的文件修改引用地址,图表只是简单封装,可根据自身功能,进行进一步配置。) …...
Phi-3-mini-4k-instruct-gguf多场景落地:跨境电商多语言商品描述批量生成
Phi-3-mini-4k-instruct-gguf多场景落地:跨境电商多语言商品描述批量生成 1. 跨境电商的痛点与解决方案 跨境电商卖家每天面临的最大挑战之一,就是为同一款商品准备不同语言版本的描述。传统做法要么需要雇佣多语种文案人员,要么使用机械的…...
告别信息混乱:Trilium中文版让知识管理像整理衣柜一样简单
告别信息混乱:Trilium中文版让知识管理像整理衣柜一样简单 【免费下载链接】trilium-translation Translation for Trilium Notes. Trilium Notes 中文适配, 体验优化 项目地址: https://gitcode.com/gh_mirrors/tr/trilium-translation 还在为英文笔记软件的…...
技能大赛备赛避坑指南:搞定软件测试五大任务(功能/自动化/性能/单元/接口)的常见错误与调试技巧
技能大赛备赛避坑指南:软件测试五大任务实战排错手册 参加职业院校技能大赛软件测试赛项的师生们,往往在备赛过程中遇到各种"坑":脚本突然报错、环境配置冲突、报告格式被扣分…这些问题看似琐碎,却可能直接影响比赛成绩…...
Chandra AI在教育领域的应用:智能学习助手开发
Chandra AI在教育领域的应用:智能学习助手开发 1. 引言 想象一下这样的场景:一个学生在深夜复习功课,遇到一道数学难题却找不到老师请教;一个上班族想学习新技能,但时间碎片化难以系统学习;一个老师面对几…...
突发!国行苹果 AI 凌晨偷跑又紧急下线
3 月 31 日凌晨,大量升级 iOS 26.4 的国行 iPhone 16 及后续机型用户,突然发现设置里 “Siri” 变成 “Apple 智能与 Siri”,可下载 9.5GB 本地 AI 模型,解锁实时翻译、视觉智能、照片消除等全套功能。不过这场“惊喜”仅持续了数…...
nlp_structbert_sentence-similarity_chinese-large保姆级教学:模型路径自定义、多模型切换、Web界面汉化配置
nlp_structbert_sentence-similarity_chinese-large保姆级教学:模型路径自定义、多模型切换、Web界面汉化配置 1. 引言:为什么需要这个工具? 你是不是经常遇到这样的情况:需要判断两段中文文字是不是表达同一个意思,…...
超级障碍马术联赛(PJL)正式启动,设立创纪录的3亿美元保底奖金池,开启障碍马术运动新纪元
• PJL助力骑手以全职职业运动员身份参赛,同时为这项运动构建可持续的经济模式。 • PJL由McCourt Global支持,核心管理团队拥有数十年马术赛事、体育和娱乐行业经验,为顶级障碍马术赛事树立全新、可持续且具备全球影响力的标准。 • 2027年3…...
嵌入式开发必知:原码、反码与补码详解
1. 为什么嵌入式开发必须掌握原码、反码和补码作为一名在嵌入式领域摸爬滚打多年的工程师,我见过太多因为不理解底层数据表示而导致的诡异bug。记得刚入行时,我调试一个温度传感器项目,当温度低于零度时,读取的数值总是偏差127度。…...
基于Python的汽车租赁管理系统毕设
博主介绍:✌ 专注于Java,python,✌关注✌私信我✌具体的问题,我会尽力帮助你。一、研究目的本研究旨在开发一套基于Python的汽车租赁管理系统,以实现汽车租赁业务的自动化、高效化和智能化。具体而言,研究目的可从以下几个方面进行…...
告别AI对话失忆症:深入LangChain4j的ChatMemoryProvider与InMemoryChatMemoryStore
深入LangChain4j记忆管理:构建高性能会话隔离系统的实践指南 在构建企业级AI对话系统时,会话记忆管理往往成为决定用户体验的关键因素。想象这样一个场景:当用户询问"我上周提到的项目进展如何?"时,系统能否…...
