最优解-最长公共子序列
问题描述
最长公共子序列(Longest Common Subsequence,LCS)即求两个序列最长的公共子序列(可以不连续)。比如3 2 1 4 5和1 2 3 4 5两个序列,最长公共子序列为2 4 5 长度为3。解决这个问题必然要使用动态规划。既然要用到动态规划,就要知道状态转移方程。我们令L[i][j] 表示序列 A 和序列 B 的最长公共子序列的长度,则状态转移方程如下:
若a[i]=b[j], 则 L[i][j]=L[i-1][j-1] +1
若a[i]!=b[j], 则 L[i][j]=max (L[i][j-1],L[i-1][j])
即:相同的取左上加1,不同取上和左中的最大值
package com.algorithm;
/*** long common Subseq*/
public class LCS {public static void main(String[] args) {char[] seq1 = new char[]{'a','b','d','c','b','a','b'};char[] seq2 = new char[]{'b','d','c','b','a','b','b'};int[][] dp = new int[seq1.length + 1][seq2.length + 1];//存储两个序列当前i和j的公共序列长度,多存储一位是空字符,默认都市0//初始化for (int i = 0; i < seq1.length + 1; i++) {dp[i][0] = 0;}for (int j = 0; j < seq2.length + 1; j++) {dp[0][j] = 0;}//计算dp,相同的取左上加1,不同取上和左中的最大值for(int i = 1; i < seq1.length; i++) {for(int j = 1; j<seq2.length; j++) {if(seq1[i] == seq2[j]) {dp[i][j] = dp[i-1][j-1]+1; //左上加1} else {dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]); //上和左中的最大值}}}//获取最长公共子序列长度,也就是dp中最大的那个值int max = 0;for(int i = 1; i < dp.length; i++) {for (int j = 1; j < dp.length; j++) {max = Math.max(max, dp[i][j]);}}System.out.println("long common seq size:"+max);}
}

从右下角开始,如果有dp[i][j]==dp[i-1][j-1]+1则往左上走一格。得到整个子序列的求解过程。b,c,b,a,b
相关文章:
最优解-最长公共子序列
问题描述 最长公共子序列(Longest Common Subsequence,LCS)即求两个序列最长的公共子序列(可以不连续)。比如3 2 1 4 5和1 2 3 4 5两个序列,最长公共子序列为2 4 5 长度为3。解决这个问题必然要使用动态规划。既然要用到动态规划,就要知道状…...
el-tree获取当前选中节点及其所有父节点的id(包含半选中父节点的id)
如下图,我们现在全勾中的有表格管理及其下的子级,而半勾中的有工作台和任务管理及其子级 现在点击保存按钮后,需要将勾中的节点id及该节点对应的父节点,祖先节点的id(包含半选中父节点的id)也都一并传给后端,那这个例子里就应该共传入9个id,我们可以直接将getCheckedK…...
新上线一个IT公司微信小程序
项目介绍 项目背景: 一家IT公司,业务包含以下六大块: 1、IT设备回收 2、IT设备租赁 3、IT设备销售 4、IT设备维修 5、IT外包 6、IT软件开发 通过小程序,提供在线下单,在线制单,在线销售,业务介绍,推广,会员 项目目的: 业务介绍: 包含企业业务介绍 客户需…...
MCAL配置-PWM(EB23.0)
PWM配置项的介绍 一、General 1、PwmDeInitApi 从代码中添加/删除Pwm_17_GtmCcu6_Delnit() API。 TRUE:Pwm_17_GtmCcu6_Delnit() API可供用户使用。 FALSE:Pwm_17_GtmCcu6_Delnit() API对用户不可用。 注意:默认情况下禁用Pwm_17_GtmCcu6_Delnit() …...
v-if和v-for哪个优先级更高?
v-if和v-for哪个优先级更高? 结论: vue2输出的渲染函数是先执行循环,在看条件判断,如果将v-if和v-for写在一个标签内,哪怕只渲染列表中的一小部分,也要重新遍历整个列表,无形造成资源浪费。vu…...
Mapstruct 常用案例(持续更新.).
将A转换为B Mapper(componentModel "spring") public interface DemoConvert {B A2B(A a); }将List转换为List 注意:以下两个都不可缺少,需要先声明单个和集合的同时生命才可 Mapper(componentModel "spring") public interface …...
QT基础篇(10)QT5网络与通信
QT5网络与通信是指在QT5开发环境中使用网络进行数据传输和通信的相关功能和技术。 QT5提供了一套完善的网络模块,包括了TCP、UDP、HTTP等协议的支持,可以方便地在QT应用程序中进行网络通信。通过QT5的网络模块,开发者可以实现客户端和服务器…...
【Leetcode】269.火星词典(Hard)
一、题目 1、题目描述 现有一种使用英语字母的火星语言,这门语言的字母顺序与英语顺序不同。 给你一个字符串列表 words ,作为这门语言的词典,words 中的字符串已经 按这门新语言的字母顺序进行了排序 。 请你根据该词典还原出此语言中已知的字母顺序,并 按字母递增顺序…...
opencv_模型训练
文件夹 opencv训练文件 xml negdataposdata 说明 negdata目录: 放负样本的目录 posdata目录: 放正样本的目录 xml目录: 新建的一个目录,为之后存放分类器文件使用 neg.txt: 负样本路径列表 pos.txt: 正样本路径列表 pos.vec: 后续自动生成…...
python PyQt5的学习
一、安装与配置 1、环境: python3.7 2、相关模块 pip install pyqt5 pyqt5-tools pyqt5designer 可以加个镜像 -i https://pypi.tuna.tsinghua.edu.cn/simple3、配置设计器 python的pyqt5提供了一个设计器,便于ui的设计 界面是这样的:…...
3.goLand基础语法
目录 概述语法for常量与变量数组切片 slice切片问题问题1问题2 Make 和 New结构体和指针结构体标签 结束 概述 从 java 转来学 go ,在此记录,方便以后翻阅。 语法 for package mainimport "fmt"func main() {for i : 0; i < 3; i {fmt.…...
计算机硬件 5.2组装整机
第二节 组装整机 一、准备工作 1.常用工具:中号十字螺丝刀、尖嘴钳、软毛刷、防静电手环等。 2.组装原则: ①按“先小后大”“从里到外”的顺序进行,不遗漏每一环节,不“带病”进行下一环节。 ②合理使用工具器材,…...
Docker搭建MySQL主从数据库-亲测有效
1、测试环境概述 1、使用MySQL5.7.35版本 2、使用Centos7操作系统 3、使用Docker20版本 案例中描述了整个测试的详细过程 2、安装Docker 2.1、如果已经安装docker,可以先卸载 yum remove -y docker \ docker-client \ docker-client-latest \ docker-common \ docker-l…...
PyTorch 中的距离函数深度解析:掌握向量间的距离和相似度计算
目录 Pytorch中Distance functions详解 pairwise_distance 用途 用法 参数 数学理论公式 示例代码 cosine_similarity 用途 用法 参数 数学理论 示例代码 输出结果 pdist 用途 用法 参数 数学理论 示例代码 总结 Pytorch中Distance functions详解 pair…...
【Vue技巧】vue3中不支持.sync语法糖的解决方案
海鲸AI-ChatGPT4.0国内站点,支持设计稿转代码:https://www.atalk-ai.com 在 Vue 3 中,.sync 修饰符已经被移除。在 Vue 2 中,.sync 修饰符是一个语法糖,用于简化子组件和父组件之间的双向数据绑定。在 Vue 3 中&#x…...
设计模式⑦ :简单化
文章目录 一、前言二、Facade 模式1. 介绍2. 应用3. 总结 三、Mediator 模式1. 介绍2. 应用3. 总结 一、前言 有时候不想动脑子,就懒得看源码又不像浪费时间所以会看看书,但是又记不住,所以决定开始写"抄书"系列。本系列大部分内容…...
Java:选择哪个Java IDE好?
Java:选择哪个Java IDE好? 在开始前我有一些资料,是我根据网友给的问题精心整理了一份「java的资料从专业入门到高级教程」, 点个关注在评论区回复“888”之后私信回复“888”,全部无偿共享给大家!!&…...
unity打包apk后网络请求提示unknown error处理
近期同事的一个比较老的版本的unity项目在电脑上运行都正常,但是打包成android后安装到手机上就提示unknown error 让我帮他排查一下问题。由于是涉密项目不能发图就简单介绍下处理过程吧! 一、故障原因 请求的地址ssl证书过期了。 二、处理过程 更改请…...
力扣 | 11. 盛最多水的容器
双指针解法–对撞指针 暴力解法public int maxArea1(int[] height) {int n height.length;int ans 0;for (int i 0; i < n; i) {for (int j i 1; j < n; j) {int area Math.min(height[i], height[j]) * (j - i);ans Math.max(ans, area);}}return ans;}双指针解法…...
史上最全EasyExcel
一、EasyExcel介绍 1、数据导入:减轻录入工作量 2、数据导出:统计信息归档 3、数据传输:异构系统之间数据传输 二、EasyExcel特点 Java领域解析、生成Excel比较有名的框架有Apache poi、jxl等。但他们都存在一个严重的问题就是非常的耗内…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
