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

176、【动态规划】leetcode ——1143. 最长公共子序列(C++版本)

题目描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
原题链接:1143. 最长公共子序列

题目描述

本题和 718. 最长重复子数组(动态规划) 的区别在于此时不要求令一个数组中元素连续。

  • 动态规划五步曲:

(1)dp[i][j]含义: 截止到text1[i - 1]text2[j - 1]时,具有的最长公共子序列。

(2)递推公式:text1[i - 1] == text2[j - 1]时,令dp[i][j] == dp[i - 1][j - 1] + 1,在上一个长度的基础上加一。不相等时,令dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]),因为i-1和j-1时不等,
缩小一个第一个的长度和第二个比缩短一个第二个的长度和第一个比,取二者中的最大长度值。

(3)dp数组初始化: dp[i][0] = dp[0][j] = 0

(4)遍历顺序: 从小到大。

(5)举例:
image.png

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n1 = text1.size(), n2 = text2.size();vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));for(int i = 1; i <= n1; i++) {for(int j = 1; j <= n2; 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[n1][n2];}
};

参考文章:1143. 最长公共子序列

相关文章:

176、【动态规划】leetcode ——1143. 最长公共子序列(C++版本)

题目描述 原题链接&#xff1a;1143. 最长公共子序列 题目描述 本题和 718. 最长重复子数组&#xff08;动态规划&#xff09; 的区别在于此时不要求令一个数组中元素连续。 动态规划五步曲&#xff1a; &#xff08;1&#xff09;dp[i][j]含义&#xff1a; 截止到text1[i …...

16行代码采集原神官网角色全图+全语音

嗨害大家好鸭&#xff01;我是小熊猫~ 本来是不玩原神的&#xff0c; 但是实在是经不住诱惑鸭~ 毕竟谁能拒绝可以爬树、炸鱼、壶里造房子、抓小动物、躲猫猫的对战游戏捏~ 准备工具 源码资料电子书:点击此处跳转文末名片获取 准备模块 import requests import re import ex…...

Unity(二)--通过简单例子了解UGUI几个常用对象操作(Text,Image,Button)

目录 文本框等UI对象的添加Canvas 画布给Canvas添加脚本,绑定要操作的对象文本框Text的使用图像Image的使用更换图片Type:显示图片相关按钮Button的使用过渡导航事件绑定文本框等UI对象的添加 Canvas 画布 所有的UI元素的父物体,。 当创建一个UI元素的时候,如果没有Canvas…...

手写一个文件上传demo

背景 最近闲来无事&#xff0c;同事闻了一下上传文件的基本操作&#xff0c;如何用文件流来实现一个文件的上传功能 基本概念 流&#xff08;Stream&#xff09;是指在计算机的输入输出操作中各部件之间的数据流动。可以按照数据传输的方向&#xff0c;将流可分为输入流和输出…...

通过 Apifox Echo 了解 Content-Length

Content-Length 用以指定 Body 的体积。响应头中的 Content-Length 指定 Response Body 的体积&#xff0c;请求头中的 Content-Length 指定 Request Body 的体积。 通过 Content-Length&#xff0c;HTTP 客户端/服务器端将会根据该头部计算出 Body 的大小。 请求头中的 Cont…...

ESP32设备驱动-CPU频率设置

CPU频率设置 文章目录 CPU频率设置1、ESP32的CPU频率介绍1.1 CPU时钟1.2 外设时钟2、CPU频率设置API3、软件准备4、硬件准备5、CPU频率设置实例5.1 CPU频率读取5.2 CPU频率设置在本文中,将介绍如何通过Arduino Core设置或更改ESP32 CPU时钟速度(频率)。 1、ESP32的CPU频率介…...

超声波风速风向传感器的技术参数

技术参数 风速 ◆ 启动风速&#xff1a;0.1m/s ◆ 测量范围&#xff1a;0&#xff5e;30m/s&#xff08;可定制&#xff09; ◆ 测量精度&#xff1a;(0.2m/s0.02*v)(v为真实风速) ◆ 分 辨 率&#xff1a;0.01m/s 风向 ◆ 测量范围&#xff1a;0&#xff5e;359 ◆ 测量精度&a…...

【vue2每日小知识】实现store中modules模块的封装与自动导入

&#x1f973;博 主&#xff1a;初映CY的前说(前端领域) &#x1f31e;个人信条&#xff1a;想要变成得到&#xff0c;中间还有做到&#xff01; &#x1f918;本文核心&#xff1a;省去我们store仓库中分模块时的需要每次导入index的问题 目录 【前言】在store中如何简…...

【Leetcode 剑指Offer】第3天 字符串(简单)

字符串剑指 Offer 05. 替换空格字符串构造函数和析构函数操作函数剑指 Offer 58 - II. 左旋转字符串剑指 Offer 05. 替换空格 题&#xff1a;实现一个函数&#xff0c;把字符串 s 中的每个空格替换成"%20"。 class Solution { public:string replaceSpace(string s…...

【双指针问题】LeetCode344、345、 844、283问题详解及代码实现

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

Linux基础命令-netstat显示网络状态

文章目录 netstat 命令介绍 语法格式 基本参数 显示各列内容分析 1&#xff09;netstat -a显示各列内容分析 2&#xff09;netstat -r显示各列内容分析 3&#xff09;netstat -i 显示各列内容分析 参考实例 1&#xff09;显示系统网络状态的所有连接 2&#xff09;…...

液氮恒温器(电学)T9015的技术规格

液氮型低温恒温器&#xff0c;利用液氮作为降温媒介&#xff0c;标准恒温器可实现快速降温至液氮温度&#xff08;约20min&#xff09;&#xff0c;其工作原理是在恒温器内部液氮腔内装入液氮&#xff0c;通过调整控温塞与冷指的间隙来保持冷指的漏热稳定在一定值上&#xff0c…...

字节跳动大规模实践埋点自动化测试框架设计

大数据时代&#xff0c;多数的web或app产品都会使用第三方或自己开发相应的数据系统&#xff0c;进行用户行为数据或其它信息数据的收集&#xff0c;在这个过程中&#xff0c;埋点是比较重要的一环。 埋点收集的数据一般有以下作用&#xff1a; 驱动决策&#xff1a;ABtest、漏…...

自动化测试优势和劣势

一、自动化测试概述 软件自动化测试是相对手工测试而存在的&#xff0c;由测试人员根据测试用例中描述的规程一步步执行测试&#xff0c;得到实际结果与期望结果的比较。在此过程中&#xff0c;节省人力、时间或硬件资源&#xff0c;提高测试效率。 二、自动化测试优势&劣…...

数据结构---顺序表

专栏&#xff1a;数据结构 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;从零开始&#xff0c;数据结构&#xff01;&#xff01; 顺序表前言接口实现SListInit初始化和SListDestory销毁SListPrint打印表中的元素SListCheckCapacity检查表中空间SListPushBack尾插和SListP…...

springboot基础

文章目录[toc]SpringBoot概述spring springmvc springboot的关系Spring Boot简介微服务springboot的优点核心功能SpringBoot搭建使用IDEA快速搭建 Spring Boot项目入门案例研究项目结构pom 文件主程序类&#xff0c;主入口类配置文件、加载顺序开启配置文件注释配置文件和加载顺…...

华为OD机试真题Python实现【 时间格式化】真题+解题思路+代码(20222023)

时间格式化 题目 运维工程师采集到某产品线网运行一天产生的日志n条 现需根据日志时间先后顺序对日志进行排序 日志时间格式为H:M:S.N H表示小时(0~23) M表示分钟(0~59) S表示秒(0~59) N表示毫秒(0~999) 时间可能并没有补全 也就是说 01:01:01.001也可能表示为1:1:1.1 🔥�…...

android kotlin 协程(五) suspend与continuation

android kotlin 协程(五) suspend与continuation 通过本篇你将学会: suspendCoroutine{} suspendCancellableCoroutine{} suspend 与 continuation suspendCoroutine 第一次看到这玩意的时候肯定有点身体不适, 先不用管这个东西是什么, 目前为止 只需要知道 suspendCoro…...

JavaScript事件循环

大厂面试题分享 面试题库后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★地址&#xff1a;前端面试题库一、异步执行原理1. 单线程的JavaScript我们知道&#xff0c;JavaScript是一种单线程语言&#xff0c;它主要用来与用户互动&#xff0c;以及操…...

华为OD机试真题Python实现【最少停车数】真题+解题思路+代码(20222023)

最少停车数 题目 特定大小的停车场 数组cars表示 其中1表示有车0表示没车 车辆大小不一,小车占一个车位(长度1) 货车占两个车位(长度2) 卡车占三个车位(长度3) 统计停车场最少可以停多少辆车 返回具体的数目 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Pyt…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》

近日&#xff0c;嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》&#xff0c;海云安高敏捷信创白盒&#xff08;SCAP&#xff09;成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天&#xff0c;网络安全已成为企业生存与发展的核心基石&#xff0c;为了解…...

Python异步编程:深入理解协程的原理与实践指南

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 持续学习&#xff0c;不断…...