LeetCode1143. Longest Common Subsequence——动态规划

news/2024/7/24 13:52:10/

文章目录

    • 一、题目
    • 二、题解

一、题目

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.
Example 2:

Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.
Example 3:

Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

二、题解

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

http://www.ppmy.cn/news/1350048.html

相关文章

C++之多线程(multi-thread)

理论基础 多线程编程是C中一个重要而复杂的主题。下面是一些建议和步骤&#xff0c;帮助你入门多线程编程&#xff1a; 了解基础概念&#xff1a; 线程和进程&#xff1a; 理解线程和进程的基本概念。 并发和并行&#xff1a; 区分并发和并行的概念&#xff0c;了解它们在多线…

没更新的日子也在努力呀,布局2024!

文章目录 ⭐ 没更新的日子也在努力呀⭐ 近期的一个状态 - 已圆满⭐ 又到了2024的许愿时间了⭐ 开发者要如何去 "创富" ⭐ 没更新的日子也在努力呀 感觉很久没有更新视频了&#xff0c;好吧&#xff0c;其实真的很久没有更新短视频了。最近的一两个月真的太忙了&#…

第一章、APPium、android自动化

第一章、APPium、android自动化 第二章、android利用QPython环境调用APPium 环境搭建 1、android studio 配置SDK Manger 的sdk、ndk、adb 控制台输入 open -e /Users/shenjianbin/.bash_profile.save export ANDROID_SDK/Users/shenjianbin/Library/Android/sdk export PA…

OCP使用web console创建和构建应用

文章目录 环境登录创建project赋予查看权限部署第一个image检查pod扩展应用 部署一个Python应用连接数据库创建secret加载数据并显示国家公园地图 清理参考 环境 RHEL 9.3Red Hat OpenShift Local 2.32 登录 在 crc start 启动crc时&#xff0c;可以看到&#xff1a; .....…

ClickHouse--02--安装

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 安装官网 &#xff1b;[https://clickhouse.com/docs/zh/getting-started/install](https://clickhouse.com/docs/zh/getting-started/install)![在这里插入图片描述…

中国电子学会2020年9月份青少年软件编程Scratch图形化等级考试试卷三级真题(编程题)

编程题(共3题&#xff0c;共30分) 36.题目&#xff1a;魔术表演“开花” 1.准备工作 &#xff08;1&#xff09;将舞台设置为"Party"&#xff1b; &#xff08;2&#xff09;删除默认角色&#xff0c;自行绘制椭圆花瓣角色&#xff1b; &#xff08;3&#xf…

C++ | KMP算法模板

next数组初始化 char a[1000006];//原串 char p[1000006];//子串 int pmt[1000006];void getNext(int m){int j0;pmt[0]0;for(int i1;i<m;i){while(j>0 && p[i]!p[j])jpmt[j-1];if(p[i]p[j])j;pmt[i]j;} }以下实例基于上述getNext函数及数据结构执行&#xff1a…

Flink从入门到实践(三):数据实时采集 - Flink MySQL CDC

文章目录 系列文章索引一、概述1、版本匹配2、导包 二、编码实现1、基本使用2、更多配置3、自定义序列化器4、Flink SQL方式 三、踩坑1、The MySQL server has a timezone offset (0 seconds ahead of UTC) which does not match the configured timezone Asia/Shanghai. 参考资…

【JVM篇】ThreadLocal中为什么要使用弱引用

文章目录 &#x1f354;ThreadLocal中为什么要使用弱引用⭐总结 &#x1f354;ThreadLocal中为什么要使用弱引用 ThreadLocal可以在线程中存放线程的本地变量&#xff0c;保证数据的线程安全 ThreadLocal是这样子保存对象的&#xff1a; 在每个线程中&#xff0c;存放了一个…

notepad++成功安装后默认显示英文怎么设置中文界面?

前几天使用电脑华为管家清理电脑后&#xff0c;发现一直使用的notepad软件变回了英文界面&#xff0c;跟刚成功安装的时候一样&#xff0c;那么应该怎么设置为中文界面呢&#xff1f;具体操作如下&#xff1a; 1、打开notepad软件&#xff0c;点击菜单栏“Settings – Prefere…

嵌入式linux驱动开发之网络设备驱动

https://bbs.csdn.net/topics/612247295 简介 Linux网络设备驱动是Linux内核中的一个重要组成部分&#xff0c;它负责网络设备的底层数据传输和设备控制。与字符设备驱动和块设备驱动相比&#xff0c;网络设备驱动的特点和功能如下&#xff1a; 首先&#xff0c;网络设备驱动…

单片机与外设的交互

单片机与外设的交互是嵌入式系统中非常重要的一个基础知识点。单片机是一个集成在同一芯片上的中央处理器、存储器和输入/输出接口,它可以根据用户编写的程序与各种外部设备即外设进行交互。单片机与外设之间的交互主要通过单片机上的输入/输出口(I/O口)来实现。 I/O口的工作原…

类和对象——封装

师从黑马程序员 封装 封装的意义一 在设计类的时候&#xff0c;属性和行为写在一起&#xff0c;表现事物 语法&#xff1a; class 类名{ 访问权限&#xff1a;属性/行为 }&#xff1b; 设计一个圆类&#xff0c;求圆的周长 代码&#xff1a; 示例1&#xff1a; #inc…

【EAI 015】CLIPort: What and Where Pathways for Robotic Manipulation

论文标题&#xff1a;CLIPort: What and Where Pathways for Robotic Manipulation 论文作者&#xff1a;Mohit Shridhar1, Lucas Manuelli, Dieter Fox1 作者单位&#xff1a;University of Washington, NVIDIA 论文原文&#xff1a;https://arxiv.org/abs/2109.12098 论文出处…

安装opencart

一、安装模板 Install SO Emarket Opencart 4 Theme 一&#xff1a;so_emarket_quick2 二&#xff1a;theme package installation 1、installed opencart Default 2、Extensions->Installer->Upload->so_emarket_theme_oc4011_home21_to_home35_v2.0.3->so_theme…

奶茶点餐|奶茶店自助点餐系统|基于微信小程序的饮品点单系统的设计与实现(源码+数据库+文档)

奶茶店自助点餐系统目录 目录 基于微信小程序的饮品点单系统的设计与实现 一、前言 二、系统功能设计 三、系统实现 1、商品信息管理 2、商品评价管理 3、商品订单管理 4、用户管理 四、数据库设计 1、实体ER图 2、具体的表设计如下所示&#xff1a; 五、核心代码 …

CSS Selector—选择方法,和html自动——异步社区的爬取(动态网页)——爬虫(get和post的区别)

这里先说一下GET请求和POST请求&#xff1a; post我们平时是要加data的也就是信息&#xff0c;你会发现我们平时百度之类的 搜索都是post请求 get我们带的是params&#xff0c;是发送我们指定的内容。 要注意是get和post请求&#xff01;&#xff01;&#xff01; 先说一下异…

跟着cherno手搓游戏引擎【24】开启2D引擎前的项目总结(包括前置知识汇总)

前置技术&#xff1a; vs属性解释&#xff1a; MSBuild的入门完整教程&#xff08;包学包会&#xff09;-CSDN博客 配置界面&#xff1a; c动态链接和静态链接&#xff1a; 隐藏的细节&#xff1a;编译与链接_哔哩哔哩_bilibili 【底层】动态链接库(dll)是如何工作的&…

基于微信小程序的在线课堂的研究与实现,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

FTP服务简介(工作原理、连接模式、流行服务器软件)

FTP&#xff08;File Transfer Protocol&#xff0c;文件传输服务&#xff09;提供在Internet上的任意两台计算机之间相互进行的文件传输。只要双方主机都支持FTP协议&#xff0c;就可以利用FTP来进行文件传输。 工作原理 FTP服务是客户/服务器模式&#xff0c;用户通过客户机…