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 版本的商用收费政策引发了广泛关注和…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
