【蓝桥云课】最长公共子序列LCS

题目描述:输入两个字符串st,求它们的最长公共子序列(不连续)。

样例输入:

BDCABA
ABCBDAB

样例输出:

4
解释:s和t的最长公共子序列为BDAB、BCAB、BCBA,长度为4

方法:
定义 d p [ i ] [ j ] dp[i][j] dp[i][j]表示 s 1 , s 2 , s 3 , . . . . , s i s_{1},s_{2},s_{3},....,s_{i} s1,s2,s3,....,si t 1 , t 2 , t 3 , . . . . , t j t_{1},t_{2},t_{3},....,t_{j} t1,t2,t3,....,tj的最长公共子序列;

那么
d p [ i + 1 ] [ j + 1 ] = { d p [ i ] [ j ] + 1 ,如果 s i + 1 = t j + 1 m a x ( d p [ i ] [ j + 1 ] , d p [ i + 1 ] [ j ] ) ,如果 s i + 1 ≠ t j + 1 dp[i+1][j+1]=\begin{cases} dp[i][j]+1& \text{,如果$s_{i+1}=t_{j+1}$}\\ max(dp[i][j+1],dp[i+1][j])& \text{,如果$s_{i+1}≠t_{j+1}$} \end{cases} dp[i+1][j+1]={dp[i][j]+1max(dp[i][j+1],dp[i+1][j]),如果si+1=tj+1,如果si+1=tj+1

程序代码:

import java.util.Arrays;
import java.util.Scanner;

public class LCS {
	
	public static void main(String[] args) {
		String s="",t="";
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			s=sc.next();
			t=sc.next();
			int[][] dp = new int[s.length()+1][t.length()+1];
			for(int i=0;i<s.length();i++) {
				for(int j=0;j<t.length();j++) {
					if(s.charAt(i)==t.charAt(j)) {
						dp[i+1][j+1]=dp[i][j]+1;
					} else {
						dp[i+1][j+1]=Math.max(dp[i][j+1], dp[i+1][j]);
					}
				}
			}
			System.out.println(dp[s.length()][t.length()]);
		}
	}
}

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

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

相关文章

win10下使用docker运行部署nginx,mysql

一、docker的步骤&#xff1a;1.进入docker官网下载安装包2.打开控制面板 - 程序和功能 - 启用或关闭Windows功能&#xff0c;勾选Hyper-V&#xff0c;然后点击确定即可&#xff0c;如图&#xff1a;3.重新启动电脑4.启动Docker在桌面找到Docker for Windows快捷方式&#xff0…

学习PCB设计前的知识扫盲

参考&#xff1a; 走进工厂&#xff1a;PCB线路板是如何制造出来的 学习PCB设计前的知识扫盲&#xff0c;新手向&#xff0c;越新手越好&#xff01; 下一步可继续学习简易的PCB绘制&#xff1a; 如何快速阅读芯片数据手册&#xff08;初学者和外行进&#xff09; 【完结】极简…

【Java】看看关于代码块的这些知识,你掌握了多少?

作者&#xff1a;努力学习的大一在校计算机专业学生&#xff0c;热爱学习和创作。目前在学习和分享&#xff1a;算法、数据结构、Java等相关知识。博主主页&#xff1a; 是瑶瑶子啦所属专栏: Java岛冒险记【从小白到大佬之路】&#xff1b;该专栏专注于Java相关知识&#xff0c…

文心一言,通营销之学,成一家之言,百度人工智能AI大数据模型文心一言Python3.10接入

“文心”取自《文心雕龙》一书的开篇&#xff0c;作者刘勰在书中引述了一个古代典故&#xff1a;春秋时期&#xff0c;鲁国有一位名叫孔文子的大夫&#xff0c;他在学问上非常有造诣&#xff0c;但是他的儿子却不学无术&#xff0c;孔文子非常痛心。 一天&#xff0c;孔文子在…

字节跳动软件测试岗,前两面过了,第三面HR天坑!竟然跟我说……

阎王易见&#xff0c;小鬼难缠。我一直相信这个世界上好人居多&#xff0c;但是也没想到自己也会在阴沟里翻船。我感觉自己被字节跳动的HR坑了。在这里&#xff0c;我只想告诫大家&#xff0c;offer一定要拿到自己的手里才是真的&#xff0c;口头offer都是不牢靠的&#xff0c;…

算法刷题总结 (四) 动态规划

算法总结4 动态规划一、动态规划1.1、基础问题11.1.1、509. 斐波那契数列1.1.2、70. 爬楼梯1.1.3、746. 使用最小花费爬楼梯1.2、基础问题21.2.1、62. 不同路径1.2.2、63. 不同路径Ⅱ1.2.3、64. 最小路径和1.2.4、343. 整数拆分1.2.5、96. 不同的二叉搜索树1.3、背包问题1.3.1、…

嵌入式学习笔记——STM32的时钟树

时钟树前言时钟树时钟分类时钟树框图LSI与LSEHSI、HSE与PLL系统时钟的产生举例AHB、APBx的时钟配置时钟树相关寄存器介绍1.时钟控制寄存器&#xff08;RCC_CR&#xff09;2.RCC PLL 配置寄存器 (RCC_PLLCFGR)3.RCC 时钟配置寄存器 (RCC_CFGR)4.RCC 时钟中断寄存器 (RCC_CIR)修改…

Java中的二叉树

文章目录前言一、树形结构&#xff08;了解&#xff09;1.1 概念1.2 概念&#xff08;重要&#xff09;1.3 树的表示形式&#xff08;了解&#xff09;1.4 树的应用二、二叉树&#xff08;重点&#xff09;2.1 概念2.2 两种特殊的二叉树2.3 二叉树的性质2.5 二叉树的存储2.5 二…

数据挖掘(2.2)--数据预处理

目录 二、数据描述 1.描述数据中心趋势 1.1平均值和截断均值 1.2加权平均值 1.3中位数&#xff08;Median&#xff09;和众数(Mode) 2.描述数据的分散程度 2.1箱线图 2.2方差和标准差 2.3正态分布 3.数据清洗 3.1数据缺失的处理 3.2数据清洗 二、数据描述 描述数…

【IDEA插件开发】环境搭建

基础信息 GRADLE 7.5.1 IDEA IntelliJ IDEA 2020.1.1 (Ultimate Edition) Build #IU-201.7223.91, built on April 30, 2020 Licensed to https://zhile.io You have a perpetual fallback license for this version Subscription is active until July 8, 2089 Runtime ve…

蓝桥杯嵌入式第一课--创建工程

概述学习本节之前&#xff0c;必须要先安装好 keil5 以及 CubeMX 等软硬件环境&#xff0c;如果你已经安装完成&#xff0c;请告诉自己&#xff1a;考试现在开始&#xff01;从CubeMX开始CubeMX是创建工程模板的软件&#xff0c;也是我们比赛时第一个要进行操作的软件。一、选择…

【十二天学java】day01-Java基础语法

day01 - Java基础语法 1. 人机交互 1.1 什么是cmd&#xff1f; 就是在windows操作系统中&#xff0c;利用命令行的方式去操作计算机。 我们可以利用cmd命令去操作计算机&#xff0c;比如&#xff1a;打开文件&#xff0c;打开文件夹&#xff0c;创建文件夹等。 1.2 如何打…

介绍两款红队常用的信息收集组合工具

介绍两款红队常用的信息收集组合工具1.Ehole本地识别FOFA识别结果输出2.AlliN1.Ehole EHole(棱洞)3.0 红队重点攻击系统指纹探测工具 EHole是一款对资产中重点系统指纹识别的工具&#xff0c;在红队作战中&#xff0c;信息收集是必不可少的环节&#xff0c;如何才能从大量的资…

【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(3)

写在前面&#xff1a; 怎么样才能学好一个算法&#xff1f; 我个人认为&#xff0c;系统性的刷题尤为重要&#xff0c; 所以&#xff0c;为了学好深度优先搜索&#xff0c;为了用好暴搜应对蓝桥杯&#xff0c; 事不宜迟&#xff0c;我们即刻开始刷题&#xff01; 题目&…

Spring Cloud Alibaba全家桶(五)——微服务组件Nacos配置中心

前言 本文小新为大家带来 微服务组件Nacos配置中心 相关知识&#xff0c;具体内容包括Nacos Config快速开始指引&#xff0c;搭建nacos-config服务&#xff0c;Config相关配置&#xff0c;配置的优先级&#xff0c;RefreshScope注解等进行详尽介绍~ 不积跬步&#xff0c;无以至…

关于Linux多线程

文章目录Linux线程的概念什么是线程二级页表线程的优点线程的缺点线程异常线程用途Linux进程VS线程进程和线程进程的多个线程共享进程和线程的关系Linux线程控制POSIX线程库线程创建线程等待线程终止分离线程Linux线程的概念 什么是线程 在一个程序里的一个执行路线就叫做线程…

【Android WMS】从应用图像获取来认识WindowState

为了能够更动感的去学习WMS窗口概念&#xff0c;这里我们从应用的图像画面获取来认识WindowState&#xff0c;作为WMS学习的一个突破口&#xff0c;现在暂时记住下面这句话&#xff0c;WindowState是WMS中的一个对象&#xff0c;保存了APP窗口相关信息。保存了窗口相关信息&…

ACM训练赛赛后补题:Happy Necklace(思维+递推+矩阵快速幂)

题目描述&#xff1a; 分析 这道题很容易就可以定性为动态规划&#xff0c;需要能够推出递推公式&#xff1b;然后观察发现n太大了&#xff0c;最多只能接收O(logn)的复杂度&#xff0c;这样的复杂度&#xff0c;实现的方式就是矩阵快速幂。 首先题目所说的是这一串项链里面…

77.qt qml-QianWindow-V1版本界面讲解

上章介绍: 76.qt qml-QianWindow开源炫酷界面框架简介(支持白色暗黑渐变自定义控件均以适配) 界面如下所示: 代码结构如下所示:

大学四年..就混了毕业证的我,出社会深感无力..辞去工作,从头开始

时间如白驹过隙&#xff0c;一恍就到了2023年&#xff0c;今天最于我来说是一个值得纪念的日子&#xff0c;因为我收获了今年的第一个offer背景18年毕业&#xff0c;二本。大学四年&#xff0c;也就将就混了毕业证和学位证。毕业后&#xff0c;并未想过留在湖南&#xff0c;就回…
最新文章