当前位置: 首页 > news >正文

最优解-最长公共子序列

问题描述

最长公共子序列(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&#xff0c;LCS)即求两个序列最长的公共子序列(可以不连续)。比如3 2 1 4 5和1 2 3 4 5两个序列&#xff0c;最长公共子序列为2 4 5 长度为3。解决这个问题必然要使用动态规划。既然要用到动态规划&#xff0c;就要知道状…...

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&#xff1a;Pwm_17_GtmCcu6_Delnit() API可供用户使用。 FALSE&#xff1a;Pwm_17_GtmCcu6_Delnit() API对用户不可用。 注意:默认情况下禁用Pwm_17_GtmCcu6_Delnit() …...

v-if和v-for哪个优先级更高?

v-if和v-for哪个优先级更高&#xff1f; 结论&#xff1a; vue2输出的渲染函数是先执行循环&#xff0c;在看条件判断&#xff0c;如果将v-if和v-for写在一个标签内&#xff0c;哪怕只渲染列表中的一小部分&#xff0c;也要重新遍历整个列表&#xff0c;无形造成资源浪费。vu…...

Mapstruct 常用案例(持续更新.).

将A转换为B Mapper(componentModel "spring") public interface DemoConvert {B A2B(A a); }将List转换为List 注意&#xff1a;以下两个都不可缺少&#xff0c;需要先声明单个和集合的同时生命才可 Mapper(componentModel "spring") public interface …...

QT基础篇(10)QT5网络与通信

QT5网络与通信是指在QT5开发环境中使用网络进行数据传输和通信的相关功能和技术。 QT5提供了一套完善的网络模块&#xff0c;包括了TCP、UDP、HTTP等协议的支持&#xff0c;可以方便地在QT应用程序中进行网络通信。通过QT5的网络模块&#xff0c;开发者可以实现客户端和服务器…...

【Leetcode】269.火星词典(Hard)

一、题目 1、题目描述 现有一种使用英语字母的火星语言,这门语言的字母顺序与英语顺序不同。 给你一个字符串列表 words ,作为这门语言的词典,words 中的字符串已经 按这门新语言的字母顺序进行了排序 。 请你根据该词典还原出此语言中已知的字母顺序,并 按字母递增顺序…...

opencv_模型训练

文件夹 opencv训练文件 xml negdataposdata 说明 negdata目录: 放负样本的目录 posdata目录&#xff1a; 放正样本的目录 xml目录&#xff1a; 新建的一个目录&#xff0c;为之后存放分类器文件使用 neg.txt: 负样本路径列表 pos.txt: 正样本路径列表 pos.vec: 后续自动生成…...

python PyQt5的学习

一、安装与配置 1、环境&#xff1a; python3.7 2、相关模块 pip install pyqt5 pyqt5-tools pyqt5designer 可以加个镜像 -i https://pypi.tuna.tsinghua.edu.cn/simple3、配置设计器 python的pyqt5提供了一个设计器&#xff0c;便于ui的设计 界面是这样的&#xff1a…...

3.goLand基础语法

目录 概述语法for常量与变量数组切片 slice切片问题问题1问题2 Make 和 New结构体和指针结构体标签 结束 概述 从 java 转来学 go &#xff0c;在此记录&#xff0c;方便以后翻阅。 语法 for package mainimport "fmt"func main() {for i : 0; i < 3; i {fmt.…...

计算机硬件 5.2组装整机

第二节 组装整机 一、准备工作 1.常用工具&#xff1a;中号十字螺丝刀、尖嘴钳、软毛刷、防静电手环等。 2.组装原则&#xff1a; ①按“先小后大”“从里到外”的顺序进行&#xff0c;不遗漏每一环节&#xff0c;不“带病”进行下一环节。 ②合理使用工具器材&#xff0c;…...

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国内站点&#xff0c;支持设计稿转代码&#xff1a;https://www.atalk-ai.com 在 Vue 3 中&#xff0c;.sync 修饰符已经被移除。在 Vue 2 中&#xff0c;.sync 修饰符是一个语法糖&#xff0c;用于简化子组件和父组件之间的双向数据绑定。在 Vue 3 中&#x…...

设计模式⑦ :简单化

文章目录 一、前言二、Facade 模式1. 介绍2. 应用3. 总结 三、Mediator 模式1. 介绍2. 应用3. 总结 一、前言 有时候不想动脑子&#xff0c;就懒得看源码又不像浪费时间所以会看看书&#xff0c;但是又记不住&#xff0c;所以决定开始写"抄书"系列。本系列大部分内容…...

Java:选择哪个Java IDE好?

Java&#xff1a;选择哪个Java IDE好? 在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「java的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&…...

unity打包apk后网络请求提示unknown error处理

近期同事的一个比较老的版本的unity项目在电脑上运行都正常&#xff0c;但是打包成android后安装到手机上就提示unknown error 让我帮他排查一下问题。由于是涉密项目不能发图就简单介绍下处理过程吧&#xff01; 一、故障原因 请求的地址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、数据导入&#xff1a;减轻录入工作量 2、数据导出&#xff1a;统计信息归档 3、数据传输&#xff1a;异构系统之间数据传输 二、EasyExcel特点 Java领域解析、生成Excel比较有名的框架有Apache poi、jxl等。但他们都存在一个严重的问题就是非常的耗内…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...