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

news/2024/2/28 17:42:34

一、动态规划

动态规划(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;
}

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

相关文章

【蓝桥杯选拔赛真题34】C++最大值 第十三届蓝桥杯青少年创意编程大赛C++编程选拔赛真题解析

目录 C/C最大值 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、推荐资料 C/C最大值 第十三届蓝桥杯青少年创意编程大赛C选拔赛真题 一、题目要求 1、编程实现&#xff08;C&#xff09; 给定一个…

【GameFramework框架内置模块】1、全局配置(Config)

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址 大家好&#xff0c;我是佛系工程师☆恬静的小魔龙☆&#xff0c;不定时更新Unity开发技巧&#xff0c;觉得有用记得一键三连哦。 一、前言 【GameFramework框架】系列教程目录&#xff1a; https://blog.csdn.net/q7…

第9讲用户信息修改实现

用户信息修改实现 后端修改用户昵称&#xff1a; /*** 更新用户昵称* param wxUserInfo* param token* return*/ RequestMapping("/updateNickName") public R updateNickName(RequestBody WxUserInfo wxUserInfo,RequestHeader String token){if(StringUtil.isNot…

vue3学习——集成sass

安装 pnpm i sass sass-loader -D在vite.config.ts文件配置: export default defineConfig({css: {preprocessorOptions: {scss: {javascriptEnabled: true,additionalData: import "./src/styles/variable.scss";,},},},} }创建三个文件 src/styles/index.scss //…

openkylin(Debian系)安装nginx及安装前需要的准备

前言 现在很多linux系统都可以使用高级包管理工具安装软件了&#xff0c;但是在像是 openkylin这些新系统中&#xff0c;好多软件包虽然有&#xff0c;但是因为其依赖的包还没有做好&#xff0c;所 以安装会提示你一大堆依赖错误。所以还是要自己来编译安装咯。安装前准备&…

【QT+QGIS跨平台编译】之三十六:【RasterLite2+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、RasterLite2介绍二、文件下载三、文件分析四、pro文件五、编译实践一、RasterLite2介绍 RasterLite2是一个开源的轻量级栅格数据库,可以用于存储和管理各种类型的栅格数据,包括卫星遥感图像、数字高程模型等。 与传统的GIS数据存储方式不同,RasterLite2采用基…

[ubuntu]split命令分割文件

split 命令 $ split --help Usage: split [OPTION]... [INPUT [PREFIX]] Output fixed-size pieces of INPUT to PREFIXaa, PREFIXab, ...; default size is 1000 lines, and default PREFIX is x. With no INPUT, or when INPUT is -, read standard input.Mandatory argume…

Java集合补充

List和array的转换 Object[] arraylist.toArray(); Integer[] array list.toArray(new Integer[3]); 注意&#xff0c;这里的3是指创建array的大小&#xff0c;当数组小的话&#xff0c;会自动扩容为刚好的大小&#xff0c;若是大了&#xff0c;剩下的空间会变为null。可以使…

STM32自学☞PWM驱动舵机(按键控制)

PWM.c文件 #include "stm32f10x.h" /*初始化函数*/ void PWM_Init(void){ /*开启时钟*/ RCC_APB1PeriphClockCmd(RCC_APB1Periph_TIM2, ENABLE); //开启TIM2的时钟 RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA, ENABLE); //开启GPIOA的时钟 /*GPIO初始化*/ G…

Redis的删除策略

在Redis中的数据删除策略有三种&#xff1a;定时删除、惰性删除、定期删除 定时删除 当key设置有过期时间&#xff0c;且过期时间到达时&#xff0c;立即执行key的删除操作 优点&#xff1a;节约内存&#xff0c;到时就删除&#xff0c;立即释放不必要的内存占用 缺点&#xf…

「数据结构」线性表

定义和基本操作 定义&#xff1a;相同数据类型的 n ( n ≥ 0 ) n(n \ge 0) n(n≥0)个数据元素的有限序列&#xff0c;其中n为表长&#xff0c;当n0时线性表是一个空表一般表示&#xff1a; L ( a 1 , a 2 , … … , a i , a i 1 , a n ) L(a_1,a_2,……,a_i,a_{i1},a_n) L(a…

django实现外键

一&#xff1a;介绍 在Django中&#xff0c;外键是通过在模型字段中使用ForeignKey来实现的。ForeignKey字段用于表示一个模型与另一个模型之间的多对一关系。这通常用于关联主键字段&#xff0c;以便在一个模型中引用另一个模型的相关记录。 下面是一个简单的例子&#xff0…

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…

​​​​​​​C#系列-C#EF框架的优缺点+针对大数据处理的优化(19)

C#EF框架的优缺点 C# EF&#xff08;Entity Framework&#xff09;框架的优缺点如下&#xff1a; 优点&#xff1a; 简单易用&#xff1a;EF框架提供了丰富的API和工具&#xff0c;使得开发者可以轻松地实现数据库的增删改查等操作&#xff0c;无需编写繁琐的SQL语句。对象化…

【Jenkins】Jenkins关闭Jenkins关闭、重启

目录 一、Jenkins关闭、重启 二、Jenkins服务的启动、停止方法。 一、Jenkins关闭、重启 1.关闭Jenkins 只需要在访问jenkins服务器的网址url地址后加上exit&#xff0c;关闭Jenkins服务。 例如&#xff1a;http://localhost:8081/exit 2.重启Jenkies 只有在Jenkins服务启动…

图像处理入门:OpenCV的基础用法解析

图像处理入门&#xff1a;OpenCV的基础用法解析 引言OpenCV的初步了解深入理解OpenCV&#xff1a;计算机视觉的开源解决方案什么是OpenCV&#xff1f;OpenCV的主要功能1. 图像处理2. 图像分析3. 结构分析和形状描述4. 动态分析5. 三维重建6. 机器学习7. 目标检测 OpenCV的应用场…

政安晨:在Jupyter中【示例演绎】Matplotlib的官方指南(二){Image tutorial}·{Python语言}

咱们接着上一篇&#xff0c;这次咱们讲使用Matplotlib绘制图像的简短尝试。 我的这个系列的上一篇文章在这里&#xff1a; 政安晨&#xff1a;在Jupyter中【示例演绎】Matplotlib的官方指南&#xff08;一&#xff09;{Pyplot tutorial}https://blog.csdn.net/snowdenkeke/ar…

ctfshow-文件上传(web151-web161)

目录 web151 web152 web153 web154 web155 web156 web157 web158 web159 web160 web161 web151 提示前台验证不可靠 那限制条件估计就是在前端设置的 上传php小马后 弹出了窗口说不支持的格式 查看源码 这一条很关键 这种不懂直接ai搜 意思就是限制了上传类型 允许…

C#系列-C#EF框架返回单行记录(24)

在C#中&#xff0c;使用Entity Framework (EF)框架时&#xff0c;如果你想要执行一个查询并返回单行记录&#xff0c;你可以使用SingleOrDefault、FirstOrDefault、Single或First方法。这些方法适用于DbSet<T>对象&#xff0c;它们可以执行查询并返回单个实体或默认值&am…
最新文章