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

动态规划 | 最长公共子序列问题

文章目录

    • 最长公共子序列
      • 题目描述
      • 问题分析
      • 程序代码
      • 复杂度分析
    • 最短编辑距离
      • 题目描述
      • 问题分析
      • 程序代码
      • 复杂度分析
    • 编辑距离
      • 题目描述
        • 输入格式
        • 输出格式
      • 问题分析
      • 程序代码

最长公共子序列

题目描述

原题链接

给定两个字符串 text1text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace""abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

问题分析

这里假设text1text2的下标均从 1 开始

状态定义dp[i][j]表示text1[1...i]text2[1...j]的最长公共子序列的长度

状态划分:根据text1[i]text2[j]是否在最长公共子序列中,可以将状态划分为四类

  1. text1[i]在,text1[j]也在:dp[i][j] = dp[i-1][j-1] + 1,同时要求text1[i] == text2[j]
  2. text1[i]在,text1[j]不在:dp[i][j] = dp[i][j-1]
  3. text1[i]不在,text1[j]在:dp[i][j] = dp[i-1][j]
  4. text1[i]不在,text1[j]也不在:dp[i][j] = dp[i-1][j-1]

由于情况 4 包含在情况 2 和情况 3 中,因此不需要要单独考虑,最终可以得到如下的状态计算。

状态计算:

  • text1[i] == text2[j]dp[i][j] = dp[i-1][j-1] + 1
  • text1[i] != text2[j]dp[i][j] = max(dp[i][j-1], dp[i-1][j])

程序代码

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));text1 = ' ' + text1;text2 = ' ' + text2;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);if( text1[i] == text2[j] ) {dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);}}}return dp[n][m];}
};

复杂度分析

时间复杂度为 O ( N 2 ) O(N^2) O(N2)

最短编辑距离

题目描述

原题链接

给你两个单词 word1word2请返回将 word1 转换成 word2 所使用的最少操作数

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

问题分析

这里假设word1word2的下标均从 1 开始

状态定义dp[i][j]表示将word1[1...i]变成word2[1...j]所需的最少操作次数

状态计算dp[i][j]可能从三种可能状态转移过来,三种状态取最小值

  • 删除操作:删除word1[i],使得 word1word2 匹配,即dp[i][j] = dp[i-1][j] + 1
  • 插入操作:在word1的末尾插入word2[j],使得二者匹配,即dp[i][j] = dp[i][j-1] + 1
  • 替换操作:word1[1...i-1]word2[1...j-1]匹配,word1[i]word2[j]有两种情况
    • word1[i] == word2[j],则无需进行替换操作,即dp[i][j] = dp[i-1][j-1]
    • word1[i] != word2[j],则需进行替换操作,即dp[i][j] = dp[i-1][j-1] + 1

边界情况

  • dp[0][0]:二者都为空,无需进行任何操作,即dp[0][0] = 0
  • dp[0][i]:表示word1为空,word1只能通过插入操作变成word2,即dp[0][i] = i
  • dp[i][0]:表示word2为空,word1只能通过删除操作变成word2,即dp[i][0] = i

程序代码

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size(), m = word2.size();int maxVal = m + n;  // 初始化数组word1 = ' ' + word1;word2 = ' ' + word2;vector<vector<int>> dp(n + 1, vector<int>(m + 1, maxVal));// 边界情况dp[0][0] = 0;for(int i = 1; i <= m; i++) {dp[0][i] = i;}for(int i = 1; i <= n; i++) {dp[i][0] = i;}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {// 删除和插入操作dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);// 替换操作if(word1[i] == word2[j]) {dp[i][j] = min(dp[i][j], dp[i-1][j-1]);}else {dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);}}}return dp[n][m];}
};

复杂度分析

时间复杂度为 O ( N 2 ) O(N^2) O(N2)

编辑距离

题目描述

给定 n 个长度不超过 10 的字符串以及 m 次询问,每次询问给出一个字符串和一个操作次数上限。

对于每次询问,请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行,每行包含一个字符串,表示给定的字符串。

再接下来 m 行,每行包含一个字符串和一个整数,表示一次询问。

字符串中只包含小写字母,且长度均不超过 10。

输出格式

输出共 m 行,每行输出一个整数作为结果,表示一次询问中满足条件的字符串个数。

问题分析

本质上其实就是最短编辑距离问题

程序代码

#include <iostream>
#include <algorithm>
using namespace std;int n, m;
const int N = 1010, INF = 1e9 + 7;
string s[N];
string p;
int k;int solve(string a, string b)
{int n = a.size(), m = b.size();a = ' ' + a;b = ' ' + b;vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));// 边界情况dp[0][0] = 0;for(int i = 1; i <= m; i++) {dp[0][i] = i;}for(int i = 1; i <= n; i++) {dp[i][0] = i;}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {// 删除和插入操作dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);// 替换操作if(a[i] == b[j]) {dp[i][j] = min(dp[i][j], dp[i-1][j-1]);}else {dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);}}}return dp[n][m];
}int main()
{cin >> n >> m;for(int i = 0; i < n; i++) {cin >> s[i];}for(int i = 0; i < m; i++) {cin >> p >> k;int cnt = 0;for(int j = 0; j < n; j++) {if( solve(s[j], p) <= k )  cnt++;}printf("%d\n", cnt);}return 0;
}

相关文章:

动态规划 | 最长公共子序列问题

文章目录 最长公共子序列题目描述问题分析程序代码复杂度分析 最短编辑距离题目描述问题分析程序代码复杂度分析 编辑距离题目描述输入格式输出格式 问题分析程序代码 最长公共子序列 题目描述 原题链接 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长 公共…...

RuntimeError: The NVIDIA driver on your system is too old.

【报错】使用 AutoDL 复现实验时遇到 RuntimeError: The NVIDIA driver on your system is too old (found version 11070). Please update your GPU driver by downloading and installing a new version from the URL: http://www.nvidia.com/Download/index.aspx Alternativ…...

Java开发过程中的幂等性问题

幂等性问题&#xff1a; 1. 有时我们在填写某些 form表单 时&#xff0c;保存按钮不小心快速点了两次&#xff0c;表中竟然产生了两条重复的数据&#xff0c;只是id不一样。 2. 我们在项目中为了解决 接口超时 问题&#xff0c;通常会引入了 重试机制 。第一次请求接口超时了…...

基于Docker的软件环境部署脚本,持续更新~

使用时CtrlF搜索你想要的环境&#xff0c;如果没有你想要的环境&#xff0c;可以评论留言&#xff0c;会尽力补充。 本文提供的部署脚本默认参数仅适合开发测试&#xff0c;请根据实际情况调节参数。 数据库 MySQL version: 3.9 services:mysql:image: mysql:8.0.35container…...

C#上位机与欧姆龙PLC的通信08----开发自己的通讯库读写数据

1、介绍 前面已经完成了7项工作&#xff1a; C#上位机与欧姆龙PLC的通信01----项目背景-CSDN博客 C#上位机与欧姆龙PLC的通信02----搭建仿真环境-CSDN博客 C#上位机与欧姆龙PLC的通信03----创建项目工程-CSDN博客 C#上位机与欧姆龙PLC的通信04---- 欧姆龙plc的存储区 C#上…...

【Redis技术专区】「原理分析」探讨Redis6.0为何需要启用多线程

探讨Redis 6.0为何需要启用多线程 背景介绍开启多线程多线程的CPU核心配置IO多线程模式单线程处理方式多线程处理方式 为什么要开启多线程&#xff1f;充分利用多核CPU提高网络I/O效率响应现代应用需求 多线程实现启用多线程 最后总结 背景介绍 在Redis 6.0版本中&#xff0c;…...

simulink代码生成(六)——多级中断的配置

假如系统中存在多个中断&#xff0c;需要合理的配置中断的优先级与中断向量表&#xff1b;在代码生成中&#xff0c;要与中断向量表对应&#xff1b;中断相关的知识参照博客&#xff1a; DSP28335学习——中断向量表的初始化_中断向量表什么时候初始化-CSDN博客 F28335中断系…...

【Minikube Prometheus】基于Prometheus Grafana监控由Minikube创建的K8S集群

文章目录 1. 系统信息参数说明2. Docker安装3. minikube安装4. kubectl安装5. Helm安装6. 启动Kubernetes集群v1.28.37. 使用helm安装Prometheus8. 使用helm安装Grafana9. Grafana的Dashboard设定10. 设定Prometheus数据源11. 导入Kubernetes Dashboard12. 实验过程中的常见问题…...

无需翻墙|Stable Diffusion WebUI 安装|AI绘画

前言 最近终于有机会从围墙里往外看&#xff0c;了解到外面的世界已经有了天翻地覆的变化&#xff0c;感叹万千&#xff0c;笔者在本地mac&#xff0c;windows&#xff0c;linux&#xff0c;docker部署了不下20遍后&#xff0c;整理出来的linux极简避坑安装方案&#xff0c;供…...

在FC中手工创建虚拟机模板

1、Linux去除个性化信息 &#xff08;1&#xff09;编辑网卡配置文件&#xff0c;只保留以下内容&#xff08;以RHEL 7为例&#xff09; &#xff08;2&#xff09;清除主机密钥信息&#xff08;开机会自动生成&#xff09; &#xff08;3&#xff09;清除Machine ID&#xff…...

OpenSSL provider

提供者 标准提供者默认提供者传统提供者FIPS 提供者基本提供者空提供者加载提供者 标准提供者 提供者是算法实现的容器。每当通过高级别 API 使用加密算法时&#xff0c;都会选择一个提供者。实际上是由该提供者实现执行所需的工作。OpenSSL 自带了五个提供者。在未来&#…...

pandas处理双周数据

处理文件题头格式 部门名称 年度名称 季节名称 商品名称 商品代码 品牌名称 品类名称 颜色名称 商店名称 0M 1L 1XL 27 28 29 2XL 30 31 32 33 3XL 4XL 5XL 6XL S 均1.导入包 导入源 pip install openpyxl -i https://pypi.doubanio.com/simple pip install pandas -i https…...

2023结婚成家,2024借势起飞

您好&#xff0c;我是码农飞哥&#xff08;wei158556&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精…...

linux SHELL语句

shell编程 shell编程 一、初识shell 程序 语言 编程语言 自然语言 汉语 英语 计算机语言 c语言cjava php python go shell 编译型语言 c c java解释型语言 php python bash (不能闭源&#xff0c;开发难度低) 编译型语言:运行编译型语言是相对于解释型语言存在的&#xff…...

音频修复和增强软件:iZotope RX 10 (Win/Mac)中文汉化版

iZotope RX 是一款专业的音频修复和增强软件&#xff0c;一直是电影和电视节目中使用的行业标准音频修复工具&#xff0c;iZotope能够帮助用户对音频进行制作、后期合成处理、混音以及对损坏的音频进行修复&#xff0c;再解锁更多功能之后还能够对电影、游戏、电视之中的音频进…...

复试 || 就业day03(2023.12.29)算法篇

文章目录 前言同构字符串存在重复元素有效的字母异位词丢失的数字单词规律 前言 &#x1f4ab;你好&#xff0c;我是辰chen&#xff0c;本文旨在准备考研复试或就业 &#x1f4ab;文章题目大多来自于 leetcode&#xff0c;当然也可能来自洛谷或其他刷题平台 &#x1f4ab;欢迎大…...

处理urllib.request.urlopen报错UnicodeEncodeError:‘ascii‘

参考&#xff1a;[Python3填坑之旅]一urllib模块网页爬虫访问中文网址出错 目录 一、报错内容 二、报错截图 三、解决方法 四、实例代码 五、运行截图 六、其他UnicodeEncodeError: ascii codec 问题 一、报错内容 UnicodeEncodeError: ascii codec cant encode charac…...

数据结构模拟实现LinkedList双向不循环链表

目录 一、双向不循环链表的概念 二、链表的接口 三、链表的方法实现 &#xff08;1&#xff09;display方法 &#xff08;2&#xff09;size方法 &#xff08;3&#xff09;contains方法 &#xff08;4&#xff09;addFirst方法 &#xff08;5&#xff09;addLast方法 …...

性能优化-如何提高cache命中率

本文主要介绍性能优化领域常见的cache的命中率问题&#xff0c;旨在全面的介绍提高cache命中率的方法&#xff0c;以供大家编写出性能友好的代码&#xff0c;并且可以应对性能优化领域的面试问题。 &#x1f3ac;个人简介&#xff1a;一个全栈工程师的升级之路&#xff01; &am…...

分布式【4. 什么是 CAP?】

什么是 CAP&#xff1f; C 代表 Consistency&#xff0c;一致性&#xff0c;是指所有节点在同一时刻的数据是相同的&#xff0c;即更新操作执行结束并响应用户完成后&#xff0c;所有节点存储的数据会保持相同。 A 代表 Availability&#xff0c;可用性&#xff0c;是指系统提…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

DeepSeek越强,Kimi越慌?

被DeepSeek吊打的Kimi&#xff0c;还有多少人在用&#xff1f; 去年&#xff0c;月之暗面创始人杨植麟别提有多风光了。90后清华学霸&#xff0c;国产大模型六小虎之一&#xff0c;手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水&#xff0c;单月光是投流就花费2个亿。 疯…...

五、jmeter脚本参数化

目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...

MySQL基本操作(续)

第3章&#xff1a;MySQL基本操作&#xff08;续&#xff09; 3.3 表操作 表是关系型数据库中存储数据的基本结构&#xff0c;由行和列组成。在MySQL中&#xff0c;表操作包括创建表、查看表结构、修改表和删除表等。本节将详细介绍这些操作。 3.3.1 创建表 在MySQL中&#…...