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

CSP-动态规划-最长公共子序列(LCS)

一、动态规划

动态规划(Dynamic Programming,简称DP)主要用于求解可以被分解为相似子问题的复杂问题,特别是在优化问题上表现出色,如最短路径、最大子数组和、编辑距离等。动态规划的核心思想是将原问题分解为较小的子问题,通过解决这些子问题,并将结果存储起来(通常是在一个数组或者哈希表中),以避免重复计算,从而提高效率。

动态规划问题的解决通常遵循以下几个步骤:

  1. 暴力穷举所有答案。
  2. 画出递归树,尝试编写递归函数求解。
  3. 若遍历中存在大量重复计算,使用哈希表缓存数据,之后遍历到相同节点就直接查表。
  4. 表示整个计算过程,观察公式求解顺序,改写成更加高效的迭代形式。

二、动态规划的例子

1.斐波那契数列

2.背包问题

3. 最长公共子序列(LCS)

  • 给定一个无序数组nums=[1,5,2,4,3],找出其中最长的递增的子序列,比如1-2-41-2-3。将问题简化,要求算法只返回最长序列的长度(3)

(1) 暴力枚举

  • 把每个子序列都“找个遍”,并且在遍历过程中实时记录当前子序列的长度
    图片描述

(2) 递归解决方案

  1. 递归函数 L:用于计算以特定元素结尾的最长递增子序列的长度;

    • 基础情形:如果当前考虑的元素是数组的最后一个元素,那么以它结尾的最长递增子序列的长度为 1,因为它自身就构成了一个长度为 1 的递增子序列。
    • 递归步骤:对于非最后一个元素,函数会遍历当前元素之后的所有元素,寻找一个值比当前元素大的元素,这意味着可以形成一个递增的序列。对于每一个这样的元素,函数会递归地计算以那个元素为结尾的最长递增子序列的长度,并将其与当前最大长度比较,更新当前最大长度。这个过程会重复直到数组结束。
    • 返回值:函数最终返回以当前元素结尾的最长递增子序列的长度。
  2. 函数 lengthOfLIS:作用是找到整个数组的最长递增子序列的长度。

    • 遍历给定数组的每个元素,对每个元素调用递归函数 L,计算以该元素为结尾的最长递增子序列的长度。
    • 比较并更新 max_len 为当前找到的最长递增子序列的长度。
    • 遍历完成后,返回 max_len 作为最终结果。
#include <iostream>
#include <vector>
using namespace std;// 计算以 nums[i] 结尾的最长递增子序列的长度
int L(const vector<int>& nums, int i) {if (i == nums.size() - 1) { // 如果是最后一个元素return 1; // 最长递增子序列长度为1}int max_len = 1; // 初始化最大长度为1for (int j = i + 1; j < nums.size(); ++j) {if (nums[j] > nums[i]) { // 如果找到一个递增的元素// 递归计算以 nums[j] 结尾的最长递增子序列长度,并加1(加上nums[i])// 然后与当前的最大长度取较大值max_len = max(max_len, L(nums, j) + 1);}}return max_len; // 返回以 nums[i] 结尾的最长递增子序列的长度
}// 计算给定序列的最长递增子序列长度
int lengthOfLIS(const vector<int>& nums) {int max_len = 0; // 初始化全局最大长度为0for (int i = 0; i < nums.size(); ++i) {// 遍历每个元素,计算以每个元素为起点的最长递增子序列的长度// 然后取所有长度中的最大值max_len = max(max_len, L(nums, i));}return max_len; // 返回最长递增子序列的长度
}int main() {vector<int> nums = {1, 5, 2, 4, 3}; cout << lengthOfLIS(nums) << endl; return 0;
}

(3) 递归的问题

  • 直接递归的方法在时间复杂度上是非常高的,因为它会重复计算很多子问题的解。
  • 比如,在遍历子序列1-2-4时就已经计算过“L(4)”,后面遍历1,4时又重复计算了一次。

(4) 递归的优化:动态规划

  • 为了避免递归中出现的重复计算,可以将第一次计算时的结果保存,之后再当遍历到相同的节点我们就不在需要重复计算,直接返回之前的结果即可。

  • 在这个版本中,L 函数中添加了一个 unordered_map (哈希表)类型的备忘录 memo,用于存储已经计算过的子问题的解。在递归的过程中,先检查备忘录是否已经包含了当前子问题的解,如果有则直接返回保存的结果,避免了重复计算。这样能够显著提高程序的性能。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;// 使用备忘录的递归方式计算以 nums[i] 结尾的最长递增子序列的长度
int L(const vector<int>& nums, int i, unordered_map<int, int>& memo) {if (i == nums.size() - 1) {return 1;}if (memo.find(i) != memo.end()) {return memo[i]; // 如果已经计算过,直接返回保存的结果}int max_len = 1;for (int j = i + 1; j < nums.size(); ++j) {if (nums[j] > nums[i]) {max_len = max(max_len, L(nums, j, memo) + 1);}}memo[i] = max_len; // 将结果保存到备忘录中return max_len;
}// 计算给定序列的最长递增子序列长度
int lengthOfLIS(const vector<int>& nums) {int max_len = 0;unordered_map<int, int> memo; // 使用unordered_map作为备忘录for (int i = 0; i < nums.size(); ++i) {max_len = max(max_len, L(nums, i, memo));}return max_len;
}int main() {vector<int> nums = {1, 5, 2, 4, 3};cout << lengthOfLIS(nums) << endl;return 0;
}

(5) 递归转非递归

  • 从后往前依次计算,即可推算出所有答案(数学归纳)
    图片描述

  • dp 数组:用于存储以每个元素结尾的最长递增子序列的长度。

  • 双重循环:外层循环遍历每个元素,内层循环遍历当前元素之前的元素,更新以当前元素结尾的最长递增子序列的长度。

  • max_element 函数:返回 dp 数组中的最大值,即整个数组中最长递增子序列的长度。

#include <iostream>
#include <vector>
using namespace std;int lengthOfLIS(const vector<int>& nums) {int n = nums.size();if (n == 0) return 0; // 处理空数组的情况vector<int> dp(n, 1); // 初始化dp数组,每个元素代表以对应位置元素结尾的最长递增子序列的长度for (int i = 1; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) {dp[i] = max(dp[i], dp[j] + 1); // 更新以nums[i]结尾的最长递增子序列长度}}}return *max_element(dp.begin(), dp.end()); // 返回dp数组中的最大值,即最长递增子序列的长度
}int main() {vector<int> nums = {1, 5, 2, 4, 3}; // 定义一个序列cout << lengthOfLIS(nums) << endl; // 输出最长递增子序列的长度return 0;
}

相关文章:

CSP-动态规划-最长公共子序列(LCS)

一、动态规划 动态规划&#xff08;Dynamic Programming&#xff0c;简称DP&#xff09;主要用于求解可以被分解为相似子问题的复杂问题&#xff0c;特别是在优化问题上表现出色&#xff0c;如最短路径、最大子数组和、编辑距离等。动态规划的核心思想是将原问题分解为较小的子…...

安装nodejs2011并配置npm仓库

1. 安装nodejs 选择2011版本下载 在安装目录(个人情况)下 D:\Program Files\nodejs2011创建2个文件夹&#xff1a; node_global &#xff08;依赖库&#xff09; node_cache &#xff08;缓存&#xff09; 然后在当前目录下cmd进入dos窗口&#xff0c;执行&#xff1a; npm c…...

排序C++代码(已更:快速排序,归并排序)

一、快速排序 #include<iostream> using namespace std;//设定三个数组&#xff0c;判断排序算法代码的正确性 int a[100]{3,4,2,6,9,7,1,0,1,2,3,3,5,6,7,8,3,4,5}; int b[100]{1,5,3,4}; int c[100]{7,8,9,1,2,3};void quickSort(int* num,int l,int r){if(l>r) re…...

CentOS 7.9安装Tesla M4驱动、CUDA和cuDNN

正文共&#xff1a;1333 字 21 图&#xff0c;预估阅读时间&#xff1a;2 分钟 上次我们在Windows上尝试用Tesla M4配置深度学习环境&#xff08;TensorFlow识别GPU难道就这么难吗&#xff1f;还是我的GPU有问题&#xff1f;&#xff09;&#xff0c;但是失败了。考虑到Windows…...

Java设计模式——策略

前言 策略模式是平时Java开发中常用的一种&#xff0c;虽然已有很多讲解设计模式的文章&#xff0c;但是这里还是写篇文章来从自己理解的角度讲解一下。 使用场景 我们不妨进行场景假设&#xff0c;要对我们的软件进行授权管理&#xff1a;在启动我们的软件之前先要校验是否…...

线性代数的本质 1 向量

向量是线性代数中最为基础的概念。 何为向量&#xff1f; 从物理上看&#xff0c; 向量就是既有大小又有方向的量&#xff0c;只要这两者一定&#xff0c;就可以在空间中随便移动。 从计算机应用的角度看&#xff0c;向量和列表很接近&#xff0c;可以用来描述某对象的几个不同…...

基于JAVA的贫困地区人口信息管理系统 开源项目

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 人口信息管理模块2.2 精准扶贫管理模块2.3 特殊群体管理模块2.4 案件信息管理模块2.5 物资补助模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 人口表3.2.2 扶贫表3.2.3 特殊群体表3.2.4 案件表3.2.5 物资补助表 四…...

【后端高频面试题--Mybatis篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 后端高频面试题--Mybatis篇 什么是Mybatis&#xff1f;Mybatis的优缺点&#xff1f;Mybatis的特点…...

【笔记】Helm-5 Chart模板指南-12 .helmignore文件

.helmignore文件 .helmignore文件用来指定您不想包含在您的helm chart中的文件。 如果该文件存在&#xff0c;helm package命令会在打包应用时忽略所有在.helmignore文件中匹配的文件。 有助于避免不需要的或敏感文件及目录添加到您的helm chart中。 .helmignore文件支持Uni…...

【MySQL】表的增删改查(基础)

MySQL表的增删改查&#xff08;基础&#xff09; 1. CRUD2. 新增&#xff08;Create&#xff09;2.1 单行数据全列插入2.2 多行数据 指定列插入 3. 查询&#xff08;Retrieve&#xff09;3.1 全列查询3.2 指定列查询3.3 查询字段为表达式3.4 别名3.5 去重&#xff1a;DISTINCT…...

Android矩阵Matrix动画缩放Bitmap移动手指触点到ImageView中心位置,Kotlin

Android矩阵Matrix动画缩放Bitmap移动手指触点到ImageView中心位置&#xff0c;Kotlin 借鉴 Android双指缩放ScaleGestureDetector检测放大因子大图移动到双指中心点ImageView区域中心&#xff0c;Kotlin&#xff08;2&#xff09;-CSDN博客 在此基础上实现手指在屏幕上点击后&…...

C语言:表达式求值

引言&#xff1a;在笔试中&#xff0c;有一类的题目&#xff0c;题目给出代码&#xff0c;要求分析得出输出结果。这类题目更加考察我们对于运算顺序和运算类型转换的理解。文章介绍了隐式类型转换和操作符注意点&#xff0c;希望增加读者对于表达式求值的理解。 1.隐式类型转…...

GO 的 Web 开发系列(五)—— 使用 Swagger 生成一份好看的接口文档

经过前面的文章&#xff0c;已经完成了 Web 系统基础功能的搭建&#xff0c;也实现了 API 接口、HTML 模板渲染等功能。接下来要做的就是使用 Swagger 工具&#xff0c;为这些 Api 接口生成一份好看的接口文档。 一、写注释 注释是 Swagger 的灵魂&#xff0c;Swagger 是通过…...

【极数系列】Flink集成KafkaSink 实时输出数据(11)

文章目录 01 引言02 连接器依赖2.1 kafka连接器依赖2.2 base基础依赖 03 使用方法04 序列化器05 指标监控06 项目源码实战6.1 包结构6.2 pom.xml依赖6.3 配置文件6.4 创建sink作业 01 引言 KafkaSink 可将数据流写入一个或多个 Kafka topic 实战源码地址,一键下载可用&#xf…...

我为什么选择Xamarin开发ios app安卓app

临岁之寒简书作者,转载 Xamarin是一项跨平台开发技术&#xff0c;之前是收费的&#xff0c;而且据说收费不菲&#xff0c;所以使用的人数比较少&#xff0c;在国内几乎无人问津。后来Xamarin被微软收购&#xff0c;现已免费开放&#xff0c;相信今后国内的使用人群会大幅地增长…...

安全基础~通用漏洞4

文章目录 知识补充XSS跨站脚本**原理****攻击类型**XSS-后台植入Cookie&表单劫持XSS-Flash钓鱼配合MSF捆绑上线ctfshow XSS靶场练习 知识补充 SQL注入小迪讲解 文件上传小迪讲解 文件上传中间件解析 XSS跨站脚本 xss平台&#xff1a; https://xss.pt/ 原理 恶意攻击者…...

2024/2/12 图的基础知识 2

目录 查找文献 P5318 【深基18.例3】查找文献 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 有向图的拓扑序列 848. 有向图的拓扑序列 - AcWing题库 最大食物链计数 P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 查找文献 P5318 【深基18.例3】…...

无人机飞行原理,多旋翼无人机飞行原理详解

多旋翼无人机升空飞行的首要条件是动力&#xff0c;有了动力才能驱动旋粪旋转&#xff0c;才能产生克服重力所必需的升力。使旋翼产生升力&#xff0c;进而推动多旋翼无人机升空飞行的一套设备装置称为动力装置&#xff0c;包括多旋翼无人机的发动机以及保证发动机正常工作所必…...

docker本地目录挂载

小命令 1、查看容器详情 docker inspect 容器名称 还是以nginx为例&#xff0c;上篇文章我们制作了nginx静态目录的数据卷&#xff0c;此时查看nginx容器时会展示出来&#xff08;docker inspect nginx 展示信息太多&#xff0c;这里只截图数据卷挂载信息&#xff09;&#…...

使用C++从零开始,自己写一个MiniWeb

第一步&#xff1a;新建项目 1、打开VS点击创建新项目 2、选择空项目并点下一步&#xff08;切记不能选错项目类型&#xff09; 3、填写项目名称和路径&#xff0c;点击创建即可 新建好后项目是这样的比较干净 4、右击源文件&#xff0c;点击添加&#xff0c;新建http.cpp文件…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#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…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

【网络安全】开源系统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…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...