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

力扣 — — 最长公共子序列

力扣 — — 最长公共子序列

最长公共子序列

  • 题源:1143. 最长公共子序列 - 力扣(LeetCode)

题目:

在这里插入图片描述

分析:

一道经典的题目:最长公共子序列(LCS)

  • 题目大意:求两个字符串的最长公共序列。

  • 算法:动态规划。

  • 思路

    1. d p dp dp 数组:设置一个数组 d p [ i ] [ j ] dp[i][j] dp[i][j],含义第一个字符串的前 i i i 个字符与第二个字符串的前 j j j 个字符的最大公共子序列。

    2. 初始化: d p [ i ] [ 0 ] = 0 dp[i][0] = 0 dp[i][0]=0 , d p [ 0 ] [ i ] = 0 dp[0][i] = 0 dp[0][i]=0 ,也就是说当第一个字符长度为 0 时,最大公共子序列为 0 ,第二个字符长度为 0 时,最大公共子序列也为 0 ;

    3. 递推公式:

      • 如果第一个字符串的第 i i i 个字符等于第二个字符的第 j j j 个字符时,将两个字符串都回退一个字符,取各自前一个字符匹配的最长公共子序列然后加 1
        d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i - 1][j - 1] + 1 dp[i][j]=dp[i1][j1]+1

      • 否则就是不相等的情况,这里也就是第一个字符串回退一个字符后与第二个字符串匹配的最长公共子序列第二个字符串回退一个字符串后与第一个字符串匹配的最长公共子序列并从这两个子序列中取最大值作为当前两个字符串匹配的最大公共子序列。
        d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) dp[i][j]=max(dp[i1][j],dp[i][j1])

代码:

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.length() + 1, vector<int>(text2.length() + 1, 0)); for(int i = 1;i <= text1.length();i ++) {for(int j = 1;j <= text2.length();j ++) {if(text1[i - 1] == text2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;}else {dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}}} return dp[text1.length()][text2.length()];}
};

相关文章:

力扣 — — 最长公共子序列

力扣 — — 最长公共子序列 最长公共子序列 题源&#xff1a;1143. 最长公共子序列 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 分析&#xff1a; 一道经典的题目&#xff1a;最长公共子序列(LCS) 题目大意&#xff1a;求两个字符串的最长公共序列。 算法&…...

通过AWS EKS 生成并部署容器化应用

今天给大家分享一个实战例子&#xff0c;如何在EKS上创建容器化应用并通过ALB来发布。先介绍一下几个基本概念&#xff1a; IAM, OpenID Connect (OIDC) 2014 年&#xff0c;AWS Identity and Access Management 增加了使用 OpenID Connect (OIDC) 的联合身份支持。此功能允许…...

GNSS静态数据处理

1 安装数据处理软件&#xff1a;仪器之星&#xff08;InStar &#xff09;和 Trimble Business Center 做完控制点静态后&#xff0c;我们需要下载GNSS数据&#xff0c;对静态数据进行处理。在处理之前需要将相关软件在自己电脑上安装好&#xff1a; 仪器之星&#xff08;InS…...

NVIDIA H100 vs A100:新一代GPU架构性能对比分析

一、核心架构演进对比 ‌Ampere架构&#xff08;A100&#xff09;‌采用台积电7nm工艺&#xff0c;集成540亿晶体管&#xff0c;配备6,912个CUDA核心和432个第三代Tensor Core&#xff0c;支持FP16、TF32和INT8精度计算。其显存子系统采用HBM2e技术&#xff0c;80GB版本带宽可…...

AI图像生成

要通过代码实现AI图像生成&#xff0c;可以使用深度学习框架如TensorFlow、PyTorch或GANs等技术。下面是一个简单的示例代码&#xff0c;演示如何使用GANs生成手写数字图像&#xff1a; import torch import torchvision import torchvision.transforms as transforms import …...

计算机考研一战上岸宁波大学经验分享

目录 话不多说先上分数 个人介绍 政治 英语二 数学二 408 复试 话不多说先上分数 初试排名15/65 复试79.81分&#xff0c;复试排名13/65 总成绩13/65&#xff0c;研招网招考50人 &#xff08;均为公开数据&#xff0c;非泄露复试信息&#xff09; 个人介绍 本人山东…...

泛微ECOLOGY9 记 数据展现集成 自定义开窗测试中对SQL 的IN语法转换存在BUG

背景 搭建流程时&#xff0c;需将明细表1中的合同字段 供明细表2中的合同开窗查询使用。 最终实现如下图&#xff1a; 选择 发票号时&#xff0c;自动带出明细表1中的采购合同号清单&#xff0c;然后在明细表2中开窗采购合同号时&#xff0c;只跳出明细表1中有的采购合同号&am…...

【Nginx】Nginx代理Tomcat配置及404问题解决

当Tomcat返回HTTP 404未找到错误时&#xff0c;可以通过以下两种方式设置跳转到指定地址&#xff1a; ① 在Tomcat应用内部配置错误页面跳转&#xff08;直接修改Tomcat的Web应用配置&#xff09; ② 在Nginx反向代理层拦截404错误并跳转&#xff08;无需修改Tomcat&#xff0c…...

【Vue】案例——To do list:

【Vue】案例——To do list&#xff1a; 一、案例介绍&#xff1a;二、效果展示&#xff08;如图&#xff09;三、主要功能&#xff1a;四、技术要点&#xff1a;补充&#xff1a;【Vue】Vue模板语法(点击可跳转)补充&#xff1a;【Vue】数据绑定&#xff08;单双向&#xff09…...

JVM不同环境不同参数配置文件覆盖

背景 需要在启动Java服务并且参数不同的场景&#xff0c;例如端口号在yml中的配置是这样的&#xff1a; server:port: 9100 覆盖配置对应JVM参数&#xff1a; java -jar xxxx.jar -Dserver.port12306 [JVM其他参数] 这样12306就会覆盖掉9100端口的配置作为启动配置 IDE…...

游戏引擎学习第215天

总结并为今天做铺垫 今天的工作内容是解决调试系统中的一个小问题。昨天我们已经完成了大部分的调试系统工作&#xff0c;但还有一个小部分没有完全处理&#xff0c;那就是关于如何层次化组织数据的问题。我们遇到的一个问题是&#xff0c;演示代码中仍有一个尚未解决的部分&a…...

C语言--求n以内的素数(质数)

求n以内的素数&#xff0c;可以用试除法或者埃拉托斯特尼筛法&#xff08;埃氏筛法&#xff09; 输入&#xff1a;数字n 输出&#xff1a;n以内所有的素数 不管是哪个方法&#xff0c;都有一个数学结论可以减少循环次数&#xff1a; 如果有一个数不是质数&#xff0c;那么它至…...

多版本go冲突问题

今天执行go build时遇到一个报错&#xff1a; compile: version “go1.22.7 (Red Hat 1.22.7-1.moduleel8.10.0700fd5cfc7a)” does not match go tool version “go1.23.4” 结果一查 which -a go 发现 当前系统居然有四个不同的位置都安装了go 于是先看go version&#xf…...

Windows 10系统出现无法使用键鼠的问题

有一位系统之家的小伙伴在升级Windows 10系统电脑的时候&#xff0c;出现键盘鼠标不能正常工作打问题&#xff0c;其实&#xff0c;遇到这个问题&#xff0c;有时只需重新启动计算机或断开连接并重新连接鼠标或键盘可以提供帮助&#xff0c;如果没有&#xff0c;可以看看下面系…...

NFC 数据传输

前言 初次接触NFC协议&#xff0c;很多人都会感觉困惑&#xff0c;搜索相关资料&#xff0c;大多数都介绍协议的理论及应用领域&#xff0c;数据传输的内容却很少&#xff0c;但对与开发人员来说&#xff0c;除了理论知识外&#xff0c;数据传输也是非常重要环节&#xff0c;尤…...

基于Streamlit的智能创业计划生成器开发实践

一、应用概述 在数字经济时代&#xff0c;创业者亟需高效工具进行系统化的商业规划。本文介绍的智能创业计划生成器基于Streamlit框架构建&#xff0c;整合了财务建模、时间轴规划、智能文档生成等核心功能。该工具通过模块化设计实现了九大创业要素的系统化配置&#xff0c;显…...

蓝桥杯单片机刷题——按键控制距离显示精度

设计要求 驱动超声波传感器&#xff0c;启动距离测量功能,并将其结果显示到数码管上&#xff0c;距离数据单位为m。 按键“S4”定义为“切换”按键&#xff0c;通过此按键切换距离的显示精度&#xff08;一位或两位小数&#xff09;。切换顺序如图所示。 数码管显示格式如下图…...

c++拷贝构造函数(深浅拷贝)+运算符重载

1拷贝构造函数 1.1定义 只有一个形参&#xff0c;且该形参是对本类类型对象的引用&#xff08;一般用const 修饰&#xff09;&#xff0c;在用已经存在的类类型对象穿件新对象是由编译器自动调用。&#xff08;是一种特殊构造&#xff0c;即初始化一个一模一样的新对象&#…...

操作系统 3.5-内存换入-请求调页

案例分析内存换入 内存换入分析&#xff1a; 内存换入&#xff08;Swapping&#xff09;是指操作系统将不常使用的内存页从物理内存&#xff08;RAM&#xff09;移动到磁盘上的交换空间&#xff08;Swap Space&#xff09;&#xff0c;以释放物理内存供其他进程使用。当需要访…...

stm32工程,拷贝到另一台电脑编译,错误提示头文件找不到cannot open source input file “core_cm4.h”

提示 cannot open source input file “core_cm4.h” ,找不到 [ core_cm4.h ] 这个头文件 . 于是我在原电脑工程文件里找也没有找到这个头文件 接下来查看原电脑keil的头文件引入配置,发现只引入了工程文件下的头文件, 那么core_cm4.h到底哪里来的? (到现在我也不清楚怎…...

使用platformio如何定位hard fault错误

这里写自定义目录标题 前言过程记录结语前言 hard fault是单片机开发过程中经常会遇到的问题,通常是内存溢出、野指针访问等导致,对于有经验的工程师,在代码改动不大的情况下,一般可以通过代码审查定位到问题原因,但也有很多情况下需要借助调试工具进行定位,像Keil就有比…...

全局异常处理器的基本使用

那使用全局异常处理器可以么&#xff1f; 是的&#xff0c;使用全局异常处理器是一个非常好的选择&#xff0c;因为它可以将异常处理逻辑集中化&#xff0c;避免在 Service 层或 Controller 层中重复编写异常处理代码。以下是使用全局异常处理器来处理添加用户时 username 唯一…...

python入门:简单介绍和python和pycharm软件安装/学习网址/pycharm设置(改成中文界面,主题,新建文件)

Python 目前是 AI 开发的首选语言 软件安装 python解释器 官网下载 Python |Python.org 勾选 Add python.exe to PATH 将python.exe添加到PATH 勾选这个选项会将Python的可执行文件路径添加到系统的环境变量PATH中。这样做的好处是&#xff0c;你可以在命令行中从任何位置直…...

众趣科技助力商家“以真示人”,让消费场景更真实透明

在当今的消费环境中&#xff0c;消费者权益保护问题日益凸显。无论是网购商品与实物不符、预定酒店民宿与图文描述差异大&#xff0c;还是游览景区遭遇“照骗”&#xff0c;这些问题不仅让消费者在消费和决策过程中倍感困扰&#xff0c;也让商家面临信任危机。 消费者在享受便…...

【Redis】string类型

目录 1、介绍2、底层实现【1】SDS【2】int编码【3】embstr编码【4】raw编码【5】embstr和raw的区别 3、常用指令【1】字符串基本操作&#xff1a;【2】批量操作【3】计数器【4】过期时间【5】不存在就插入 4、使用场景 1、介绍 string是redis中最简单的键值对形式&#xff0c;…...

EPLAN许可证更新教程

随着电气设计软件的不断更新和优化&#xff0c;确保您的EPLAN许可证始终是最新版本对于顺畅的项目管理至关重要。本文将为您提供一份详尽的EPLAN许可证更新教程&#xff0c;帮助您轻松完成更新操作&#xff0c;确保您的软件始终保持最佳状态。 一、为什么需要更新EPLAN许可证&…...

学习笔记五——Rust 控制流全解析

&#x1f4da; 目录 什么是控制流&#xff1f;Rust 有什么特别&#xff1f;if 表达式完整语法loop / while / for 三种循环写法match 表达式 _ 通配符深入解释if let 表达式用法与场景Option、Some、None 全面通俗讲解 "Tom" 和 "Tom".to_string() 有啥本…...

远程桌面协议(RDP)详解:原理、优势与局限和优化方案分享

文章目录 导言一. RDP的工作原理二. RDP的优势三. RDP的局限性四. RDP的优化与替代方案五. 内网穿透远程访问总结 导言 远程桌面协议(RDP)是一种微软开发的专有协议&#xff0c;允许用户通过网络连接到另一台计算机&#xff0c;并像操作本地计算机一样进行操作。它广泛应用于远…...

Linux 系统管理常用命令

以下是 Linux 系统管理常用命令 的详细介绍&#xff0c;涵盖 IP地址查看、端口管理、进程监控 等核心操作&#xff0c;并附上实际示例&#xff1a; 一、查看网卡 IP 地址 1. 使用 ip 命令 # 查看所有网络接口信息&#xff08;包括 IP 地址&#xff09; ip addr show# 查看特定…...

蓝桥杯篇---客观题

文章目录 前言 前言 本文简单介绍了蓝桥杯中客观题各个部分的知识点。 一、单片机相关 IAP15F2K61S2单片机的定时器0具有4种工作模式&#xff0c;当采用外部12MHz晶振时&#xff0c;定时器最大定时长度65535us。8051单片机的P0口&#xff0c;当使用外部存储器时它是一个传输低…...

RK3568 基于Gstreamer的多媒体调试记录

文章目录 1、环境介绍2、概念理清3、提前准备4、GStreamer编译5、GStreamer基础介绍6、视频播放初体验7、视频硬编码7.1、h2647.2、h265 8、视频硬解码8.1、解码视频并播放解码视频并播放带音频 1、环境介绍 硬件&#xff1a;飞凌ok3568-c开发板 软件&#xff1a;原厂rk356x …...

ZYNQ笔记(五):AXI GPIO 中断

版本&#xff1a;Vivado2020.2&#xff08;Vitis&#xff09; 任务&#xff1a;使用 AXI GPIO IP 核以中断方式实现按键 KEY 控制 LED 亮灭翻转&#xff08;两个都在PL端&#xff09; 目录 一、介绍 二、硬件设计 三、软件设计 四、效果 一、介绍 AXI GPIO 中断通常…...

C++23 多维下标运算符:探索 P2128R6 提案

文章目录 一、背景与动机二、语法与实现2.1 语法2.2 实现方式 三、应用场景3.1 多维数组3.2 自定义数据结构3.3 并行计算 四、性能影响4.1 编译时优化4.2 自定义数据结构的优化 五、总结 C23 引入了许多新特性&#xff0c;其中之一便是多维下标运算符&#xff08;P2128R6&#…...

原理图设计准备:页面栅格模板应用设置

一、页面大小的设置 &#xff08;1&#xff09;单页原理图页面设置 首先&#xff0c;选中需要更改页面尺寸的那一页原理图&#xff0c;鼠标右键&#xff0c;选择“Schmatic Page Properties”选项&#xff0c;进行页面大小设置。 &#xff08;2&#xff09;对整个原理图页面设…...

LeeCode 409.最长回文串

给定一个包含大写字母和小写字母的字符串 s &#xff0c;返回 通过这些字母构造成的 最长的 回文串 的长度。 在构造过程中&#xff0c;请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1: 输入:s "abccccdd" 输出:7 解释: 我们可以构造的…...

保护PCBA的不同方法:喷三防漆 vs 镀膜

PCBA&#xff08;印刷电路板组件&#xff09;的防护工艺中&#xff0c;喷三防漆和镀膜&#xff08;如Parylene气相沉积&#xff09;是两种常见技 术。它们在防护目的上类似&#xff0c;但在具体实现方式和应用场景上有显著差异。以下从外观、工艺、性 能、物理性质和成本五个…...

XILINX FPGA万兆光电口PXIE板卡设计

主要性能指标 1、 FPGA 型号&#xff1a; XC7K325-TFFG676-2 &#xff1b; 2、 网络端口速率 &#xff1a; 10Gbps/1Gbps/2.5Gbps &#xff1b; 3、 网络端口形式 &#xff1a; 3 路 SFP 万兆光电口 &#xff1b; 4、 内存数量&#xff1a; 4Gb 4 &#xff1b; 5、 内存带宽&…...

LangChain4j实战-Java AI应用开源框架之LangChain4j和Spring AI

今天这篇文章我来分享LangChain4j实战-Java AI应用开源框架之LangChain4j和Spring AI。 在贝恩聊架构AI专栏中通过学习如何使用Java相关AI应用开源框架&#xff0c;到后续开发企业级Java AI应用&#xff0c;将大型语言模型和AI工具集成到现有系统中。我们将重点介绍如何使用Sp…...

机器学习十大算法全解析机器学习,作为人工智能的基石,涵盖了众多高效的算法。今天,我们就来深入探讨其中的十大核心算法!

1️⃣ 线性回归&#xff1a;通过最小化误差的平方和来寻找最佳函数匹配。 2️⃣ 逻辑回归&#xff1a;用于分类问题&#xff0c;通过逻辑函数来预测事件发生的概率。 3️⃣ 决策树&#xff1a;基于特征选择和阈值来构建树形结构&#xff0c;用于分类和回归。 4️⃣ 朴素贝叶…...

day26图像处理OpenCV

文章目录 一、OpenCV1.介绍2.下载3.图像的表示4.图像的基本操作4.1图片读取或创建4.1.1读取4.1.2创建 4.2创建窗口4.3显示图片4.3.1设置读取的图片4.3.2设置显示多久4.3.3释放 4.4.保存图片4.5图片切片&#xff08;剪裁&#xff09;4.6图片大小调节 5.在图像中绘值5.1绘制直线5…...

怎么查询SQL Server AlwaysOn

1. SQL Server AlwaysOn 是什么&#xff1f; SQL Server AlwaysOn 是 Microsoft 提供的高可用性&#xff08;High Availability, HA&#xff09;和灾难恢复&#xff08;Disaster Recovery, DR&#xff09;解决方案&#xff0c;包含以下两个核心技术&#xff1a; 组件描述故障…...

10分钟做了一个投资回报计算器,欢迎大家使用

一、背景 今天突然想算一下1万本金&#xff0c;2%利率存2年情况下的投资回报收益情况&#xff0c;但是发现手上没有计算器&#xff0c;想着自己做一个网页简单实现一下&#xff0c;于是有了这个小工具&#xff08;FutureValueCalculator——未来价值计算器&#xff09;。 二、…...

报错:mount: unknown filesystem type ‘vfat’

服务器重启之后 进入 Ctrl D 界面 界面报错是 FAILED to mount /boot/efi 输入密码进去之后 (py38) [rootlocalhost data]# lsblk NAME MAJ:MIN RM SIZE RO TYPE MOUNTPOINTS sda 8:0 0 1.5T 0 disk ├─sda1 8:1 0 50M 0 part /bo…...

Java学习手册:面向对象编程核心概念

面向对象编程&#xff08;OOP&#xff09;是Java语言的核心编程范式&#xff0c;它强调通过对象之间的交互来实现程序功能。OOP的核心思想是将现实世界中的事物抽象为对象&#xff0c;通过对象的属性和行为来描述和操作这些事物。本文将深入探讨Java中面向对象编程的三大核心概…...

工厂模式(简单工厂,工厂方法,抽象工厂)

工厂模式 工厂模式是java中最常用的设计模式&#xff0c;主要是用来完成对象的创建&#xff0c;使得对象创建过程和对象使用过程分离。 简单来说是取消对象创建者和使用者的耦合&#xff0c;简化new 对象的创建。 优势 &#xff1a;对象的属性创建完整。 缺点&#xff1a; 创建…...

【实际项目分享】多相机取图存图问题

1、项目介绍 针对 ​​5路相机同步取图​​ 场景&#xff0c;设计了一套高并发、低延迟的图像数据管理方案&#xff0c;重点解决多线程环境下的数据竞争与存储效率问题。 2、设计目标​​ ​​高并发写入​​&#xff1a;支持5个相机线程同时写入数据&#xff0c;无锁冲突​​…...

LLMs基础学习(七)DeepSeek专题(1)

LLMs基础学习&#xff08;七&#xff09;DeepSeek专题&#xff08;1&#xff09; 文章目录 LLMs基础学习&#xff08;七&#xff09;DeepSeek专题&#xff08;1&#xff09;DeepSeek 相关资料官方资料与基础文档实践指南和技术解析 热启动与冷启动**热启动&#xff08;主流&…...

安装vllm

ubuntu 22.04, RTX3080, cuda 12.1, cudnn 8.9.7&#xff0c;cuda和cudnn的安装参考&#xff1a;https://blog.csdn.net/m0_52111823/article/details/147154526?spm1001.2014.3001.5501。 查看版本对应关系&#xff0c;下载12.1对应的whl包&#xff0c;https://github.com/vl…...

SVMSPro分布式综合安防管理平台--地图赋能智慧指挥调度新高度

SVMSPro分布式综合安防管理平台–地图赋能智慧指挥调度新高度 在智慧城市建设和公共安全需求日益增长的背景下&#xff0c;SVMSPro分布式综合安防管理平台凭借其强大的地图功能与多协议兼容能力&#xff0c;正在成为公安、司法、消防、城管、交通等领域的指挥调度“智慧大脑”…...

科技快讯 | OpenAI:向Plus和Pro用户推出ChatGPT记忆提升功能;我国成功发射通信技术试验卫星十七号;芯片国产化率超九成

继 OpenAI 后&#xff0c;谷歌 Gemini 模型将支持 Anthropic 的 MCP 协议 4月10日&#xff0c;谷歌DeepMind宣布将支持Anthropic的模型上下文协议&#xff08;MCP&#xff09;&#xff0c;以实现大语言模型与外部数据源的集成。MCP由Anthropic推出&#xff0c;旨在建立安全双向…...