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

刷代码随想录有感(125):动态规划——最长公共子序列

题干:

代码:

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

递推公式:如果相同,则后一个为前一个长度加一;如果不相同(如图c不等于e),情况一:考虑c不考虑e,则变成abc与ac的最长公共子序列,此时为dp[i][j-1]; 情况二:考虑e不考虑c,则变成ace与ab的最长公共子序列,此时为dp[i-1][j]。综上最后dp[i][j]取他们当中最大的一个。

定义:dp[i][[j]为以 i - 1和j - 1为结尾的最长公共子序列长度。

相关文章:

刷代码随想录有感(125):动态规划——最长公共子序列

题干&#xff1a; 代码&#xff1a; class Solution { public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>>dp(text1.size() 1, vector<int>(text2.size() 1, 0));for(int i 1; i < text1.size(); i){for(int j …...

Linux和mysql中的基础知识

cpu读取的指令大部分在内存中&#xff08;不考虑缓存&#xff09; 任何程序在运行之前都的加入到内存。 eip->pc指针&#xff0c;指明当前指令在什么位置。 代码大概率是从上往下执行的&#xff0c;基于这样的基本理论。既可以将一部分指令加载到CPU对应的缓存中&#xf…...

ArcGIS Pro SDK (七)编辑 12 编辑模版

ArcGIS Pro SDK &#xff08;七&#xff09;编辑 12 编辑模版 文章目录 ArcGIS Pro SDK &#xff08;七&#xff09;编辑 12 编辑模版1 在图层上按名称查找编辑模板2 查找属于独立表的表模板3 当前模板4 更改模板的默认编辑工具5 隐藏或显示模板上的编辑工具6 使用图层创建新模…...

数据结构底层之HashMap(面经篇1)

1 . 讲一下hashmap的数据结构 HashMap是一种基于哈希表实现的数据结构&#xff0c;通常用于关联键值对&#xff0c;其中键是唯一的&#xff0c;而值可以重复。在Java中&#xff0c;HashMap是java.util.Map接口的一个实现&#xff0c;它提供了快速的查找、插入和删除操作。 数据…...

昇思学习打卡-6-基于MindSpore的GPT2文本摘要

第一次近距离接触GPT&#xff0c;了解了tokenizers这个分词库&#xff0c;感觉NLP和CV对比起来&#xff0c;处理流程基本一致&#xff0c;都是数据集加载和处理&#xff0c;模型构建、选择学习率、模型训练&#xff0c;进而可以使用模型进行推理。 不同的是&#xff0c;NLP可能…...

代码随想录算法训练营第2天|LeetCode977,209,59

977.有序数组平方 题目链接&#xff1a; 977. 有序数组的平方 - 力扣&#xff08;LeetCode&#xff09; 文章讲解&#xff1a;代码随想录 视频讲解&#xff1a; 双指针法经典题目 | LeetCode&#xff1a;977.有序数组的平方_哔哩哔哩_bilibili 第一想法 暴力算法肯定是先将元素…...

Web前端开发——HTML快速入门

HTML&#xff1a;控制网页的结构CSS&#xff1a;控制网页的表现 一、什么是HTML、CSS &#xff08;1&#xff09;HTML &#xff08;HyperText Markup Languaqe&#xff1a;超文本标记语言&#xff09; 超文本&#xff1a;超越了文本的限制&#xff0c;比普通文本更强大。除了…...

浅谈http协议及常见的面试题

1、浅谈http协议 HTTP&#xff08;Hypertext Transfer Protocol&#xff09;超文本传输协议&#xff0c;是互联网上应用最为广泛的一种网络协议&#xff0c;所有的WWW文件都必须遵守这个标准。它是基于TCP/IP通信协议来传递数据&#xff08;HTML文件、图片文件、查询结果等&am…...

LabVIEW自动探头外观检测

开发了一套基于LabVIEW的软件系统&#xff0c;结合视觉检测技术&#xff0c;实现探头及连接器外观的自动检测。通过使用高分辨率工业相机、光源和机械手臂&#xff0c;系统能够自动定位并检测探头表面的细微缺陷&#xff0c;如划痕、残胶、异色、杂物等。系统支持多种探头形态&…...

搏击与防卫笔记

文章目录 降龙十八掌 咏春个人防身笔记防卫直拳应对耳光防卫摆拳坐马冲拳 本来想以武术为标题的&#xff0c;想了想武术这个标题太大太深&#xff0c;自己连一知半解都算不上&#xff0c;就谢为搏击与防卫吧。 每个男孩都有个武侠梦&#xff0c;独步江湖&#xff0c;仗剑走天涯…...

泰国内部安全行动司令部数据泄露

BreachForums 论坛的一名成员宣布发生一起重大数据泄露事件&#xff0c;涉及泰国内部安全行动司令部 (ISOC)&#xff0c;该机构被称为泰国皇家武装部队的政治部门。 目前&#xff0c;我们无法准确确认此次泄露的真实性&#xff0c;因为该组织尚未在其网站上发布有关该事件的任…...

MATLAB算法实战应用案例精讲-【数模应用】分层聚类(附MATLAB、python和R语言代码实现)

目录 前言 几个高频面试题目 什么情况下选择分层聚类,什么情况下选择K-mean聚类呢?两种模型的好坏如何比较? 算法原理 SPSSAU 案例分析 SPSSPRO 1、作用 2、输入输出描述 3、案例示例 4、案例数据 5、案例操作 6、输出结果分析 7、注意事项 8、模型理论 分层…...

九、函数的声明和定义

函数声明&#xff1a; 1. 告诉编译器有一个函数叫什么&#xff0c;参数是什么&#xff0c;返回类型是什么。但是具体是不是存在&#xff0c;函数 声明决定不了。 2. 函数的声明一般出现在函数的使用之前。要满足先声明后使用。 3. 函数的声明一般要放在头文件中的。 定义的函…...

简洁纯文字类的Typecho主题wenso

主题介绍 文章说说类博客网站源码&#xff0c;页面清新简洁。适合文章说说美文博客网站建站使用&#xff0c;响应式手机版本。 本来是dedecms的模板&#xff0c;也比较简单&#xff0c;适合用来搭建一个文学类的&#xff0c;纯文字的网站&#xff0c;简单的改成了typecho&…...

安卓请求服务器[根据服务器的内容来更新spinner]

根据服务器的内容来更新spinner 本文内容请结合如下两篇文章一起看: 腾讯云函数node.js返回自动带反斜杠 腾讯云函数部署环境[使用函数URL] 现在有这样一个需求,APP有一个下拉选择框作为版本选择,因为改个管脚就变成一个版本,客户需求也很零散,所以后期会大量增加版本,这时候每…...

c++ 联合(Union)的特性和使用

联合&#xff08;Union&#xff09;是一种特殊的数据结构&#xff0c;允许在同一内存位置存储不同的数据类型。一个 union 可以有多个数据成员&#xff0c;但是在任意时刻只有一个数据成员可以有值。当某个成员被赋值后其他成员变为未定义状态。以下是联合的主要特点和使用方式…...

大白菜U盘启动工具

大白菜如何u盘启动进winpe装系统大白菜是一款非常实用的U盘启动盘制作工具&#xff0c;可以帮助用户快速地将U盘制作成启动盘&#xff0c;从而方便地进行系统安装、维护和修复等操作。官方网站&#xff1a; 大白菜u盘启动盘制作工具_大白菜u盘装系统_大白菜pe_大白菜官网-首页…...

C# 中 IEnumerable 和 IQueryable 接口之间的区别

在 C# 中&#xff0c;IEnumerable和IQueryable接口都用于查询数据集合&#xff0c;但它们的用途不同&#xff0c;功能也不同。下面是它们之间差异的细分&#xff1a; 1. C# 中的 IEnumerable 接口 在命名空间中定义System.Collections。表示集合中元素的只进式游标。适用于查…...

centos安装yum命令及常用yum命令

一、准备工作 获取安装介质&#xff1a; 如果你有CentOS的安装ISO文件或DVD介质&#xff0c;可以直接使用它来设置本地yum源。 如果没有&#xff0c;你需要在一个有网络连接的CentOS系统上下载所需的rpm包和依赖。 创建挂载点&#xff08;如果你使用的是ISO文件&#xff09;&a…...

table = collections.defaultdict(list)申请的字典的类型是什么?

当你使用 collections.defaultdict(list) 来申请一个字典时&#xff0c;这个字典的类型是 defaultdict&#xff0c;但是其行为和表现方式在某些方面与普通的字典&#xff08;dict&#xff09;相似&#xff0c;主要区别在于它如何处理缺失的键。 defaultdict 是 Python 标准库 …...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...