leetcode hot100 之 最长公共子序列
题目
给定两个字符串 text1
和 text2
,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
示例 1:
输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace” ,它的长度为 3 。
原题链接:https://leetcode.cn/problems/longest-common-subsequence/description/
思路
以 dp[i][j] 表示,text1[0:i] 和 text2[0:j] 的最长公共子序列长度。
找转移方程:
当 text[i] == text[j] 时,即两个子字符串末尾的字符相同时,dp[i][j] = dp[i-1][j-1] + 1。
当 text[i] != text[j] 时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
找边界条件:
当 i=0 或 j=0 时,显然可得 dp[i][0]、dp[0][j] = 0
代码
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size();int n = text2.size();vector<vector<int>> dp(m+1, vector<int> (n+1, 0));// 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])for (int i = 0; i <= m; i++) {dp[i][0] = 0;}for (int j = 0; j <= n; j++) {dp[0][j] = 0;}for (int i = 1; i <= m; i++) {for (int j = 1; j <=n; j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i-1][j-1] + 1;} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}}return dp[m][n];}
};
相关文章:
leetcode hot100 之 最长公共子序列
题目 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(…...

短剧APP开发,新的“财富”
在数字化时代,开发短剧APP不仅是顺应潮流的必然选择,更是抓住市场机遇的关键所在。为确保短剧APP能有效地吸引并留住用户,以下是一些主要功能及其介绍: 1、短剧搜索 关键词搜索:用户可以通过输入关键词(如…...
Uniapp与第三方应用数据通讯
首先说明一点,这个只是uniapp代码编写的应用之间相互传递数据,uniapp编写的与其他语言编写的我尚不知道能不能传递。 应用1: plus.runtime.launchApplication({pname: "应用的appid",// extra 中可以自定数据,url和da…...

AI大模型战场:通用大模型与垂直大模型的角逐
随着人工智能技术的迅猛发展,AI大模型已成为推动科技进步的重要力量。然而,在AI大模型的战场上,通用大模型与垂直大模型之间的分化日益明显。两者各有其独特的优势和潜力,在不同的应用场景中发挥着重要作用。那么,在这…...
linux的一些知识点分享-------关于操作维护的一些知识点
Apache服务器的监听端口,默认为() Apache服务器的监听端口,默认为80。 vsftpd中,可以不需提供账号密码就能进行访问的用户是( ) 在vsftpd(Very Secure FTP Daemon)中,可以不需要提供账号密码就能进行访问的用户通常是匿名用户。…...

Python使用tkinter库设置背景图片、label显示位置和label设置显示图片
tkinter 设置背景图片 label显示位置 label设置显示图片 from tkinter import * import tkinter as tk from PIL import ImageTk from PIL import Imagedef get_img(filename, width, height):im Image.open(filename).resize((width, height))im ImageTk.PhotoImage(im)…...
OpenStack是什么?
OpenStack是一个开源的云计算管理平台项目,它是一系列软件开源项目的组合。该项目由美国国家航空航天局(NASA)和Rackspace合作研发并发起,旨在提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenStack不仅是一个软…...

2024下《系统规划与管理师》50个高频考点汇总!背就有效
2024上半年软考考试已经结束,有不少小伙伴已经开始准备下半年软考了,但是大家要注意:今年高项仅考上半年一次,下半年考的高级科目只有系规难度相对较低,系规需要学习的内容比高项少很多,高项第四版教程731页…...

软件游戏提示msvcp140.dll丢失的原因分析及解决方法
在计算机使用过程中,我们经常会遇到一些错误提示,其中之一就是“计算机缺失msvcp140.dll”。那么,这个错误是什么意思呢?它会造成哪些问题?小编将从以下几个方面进行详细解析。 一,了解msvcp140.dll是什么 …...
备战 清华大学 上机编程考试-冲刺前50%,倒数第3天
T1:水滴 - 模拟 这是一个经典的游戏。 在一个 𝑛𝑚 的棋盘上,每一个格子中都有一些水滴。 玩家的操作是,在一个格子中加一滴水。 当一个格子中的水滴数超过了 4,这一大滴水就会因格子承载不住而向外扩散。扩散的规…...
docker的安装及docker常用命令
目录 环境介绍docker卸载docker安装docker镜像命令查看docker可用的镜像查看docker可安装的镜像安装镜像删除镜像 docker容器命令查看容器启动容器启动示例进入容器内部停止容器删除容器容器和主机之间的文件复制 docker网络命令创建docker网络查看docker网络删除docker网络 do…...

Dell服务器根据GPU温度调整风扇转速
前言 dell服务器自动风扇是根据CPU温度来调速的,我跑AI的时候cpu温度不高但是GPU温度很高导致显卡卡死PVE虚拟机直接挂起无法运行,我看了下也没有基于显卡温度调速的脚本,于是我就自己写了一个 基于ipmi工具 乌班图等linux先安装ipmi apt …...

快捷键专栏 IDEA、Navicat、电脑、Excle、Word等
标题 电脑篇windowsR 配合以下常用命令连上公司网线WiFi速度变慢问题解决Windows10 设置鼠标右键在此处打开cmd和Powershell窗口、关机打开电脑诊断工具系统设置常用设置查看电脑出场日期 systeminfo删除文件显示已在另一个程序打开?找回回收站删除的文件WindowsR输…...

卸载MySQL5.0,安装MySQL8.0
卸载MySQL 1、以管理员身份运行cmd,删除MySQL服务 2、卸载MySQL 3、删除残余文件 4、清楚注册表 winR -> regedit 5、删除环境变量 安装MySQL步骤 官方下载地址 https://www.mysql.com/downloads/ 以上步骤即完成MySQL数据库安装。...

苹果WWDC重磅发布的IOS 18、Apple Intelligence背后的技术分析!
2024年6月10日,在2024年WWDC全球开发者大会上,苹果推出了Apple Intelligence,这是深度集成到iOS 18、iPadOS 18和macOS Sequoia中的个人智能系统。 为了让大模型能在 iPhone 端侧跑,苹果还是做了很多事情的。接下来就跟大家介绍一…...

Linux基础IO【II】
今天,我们接着在上一篇文章的基础上,继续学习基础IO。观看本文章之前,建议先看:Linux基础IO【I】,那,我们就开始吧! 一.文件描述符 1.重新理解文件 文件操作的本质:进程和被打开文件…...
DevExpress学习系列文章
一:DevExpress Installed 二:Application UI 三:Data Management Controls 四:Skins 五:DevExpress 控件和库 系列文章相关代码:DevExpressDemo: DevExpress学习过程中的Demo...
在大数据时代:为何硬盘仍是数据中心存储的核心
在云计算和人工智能应用场景不断涌现的时代背景下,数据集的价值急剧上升,硬盘对于数据中心运营商来说变得比以往任何时候都更为关键。硬盘存储了全球大部分的艾字节(EB)数据,行业分析师预计,在艾字节持续增…...
安装TrinityCore NPCBot(尝试中)
安装TrinityCore NPCBot 基本安装方法 Follow TrinityCore Installation Guide (https://TrinityCore.info/) to install the server firstDownload NPCBots.patch and put it into your TrinityCore folderApply the patch using patch -p1 < NPCBots.patch command (crea…...

Java SE LTS版本商用收费,有那些开源的替代方案?
🚀 Java SE LTS版本商用收费,有那些开源的替代方案? 摘要 Java 对于云服务、大数据、电子商务、支付、欺诈和身份、交易等许多应用程序来说都是至关重要的语言。然而,Oracle 对 Java SE LTS 版本的商用收费政策引发了广泛关注和…...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...

c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...