CSP-动态规划-最长公共子序列(LCS)
一、动态规划
动态规划(Dynamic Programming,简称DP)主要用于求解可以被分解为相似子问题的复杂问题,特别是在优化问题上表现出色,如最短路径、最大子数组和、编辑距离等。动态规划的核心思想是将原问题分解为较小的子问题,通过解决这些子问题,并将结果存储起来(通常是在一个数组或者哈希表中),以避免重复计算,从而提高效率。
动态规划问题的解决通常遵循以下几个步骤:
- 暴力穷举所有答案。
- 画出递归树,尝试编写递归函数求解。
- 若遍历中存在大量重复计算,使用哈希表缓存数据,之后遍历到相同节点就直接查表。
- 表示整个计算过程,观察公式求解顺序,改写成更加高效的迭代形式。
二、动态规划的例子
1.斐波那契数列
2.背包问题
3. 最长公共子序列(LCS)
- 给定一个无序数组
nums=[1,5,2,4,3]
,找出其中最长的递增的子序列,比如1-2-4
,1-2-3
。将问题简化,要求算法只返回最长序列的长度(3)
(1) 暴力枚举
- 把每个子序列都“找个遍”,并且在遍历过程中实时记录当前子序列的长度
(2) 递归解决方案
-
递归函数
L
:用于计算以特定元素结尾的最长递增子序列的长度;- 基础情形:如果当前考虑的元素是数组的最后一个元素,那么以它结尾的最长递增子序列的长度为 1,因为它自身就构成了一个长度为 1 的递增子序列。
- 递归步骤:对于非最后一个元素,函数会遍历当前元素之后的所有元素,寻找一个值比当前元素大的元素,这意味着可以形成一个递增的序列。对于每一个这样的元素,函数会递归地计算以那个元素为结尾的最长递增子序列的长度,并将其与当前最大长度比较,更新当前最大长度。这个过程会重复直到数组结束。
- 返回值:函数最终返回以当前元素结尾的最长递增子序列的长度。
-
函数
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)
一、动态规划 动态规划(Dynamic Programming,简称DP)主要用于求解可以被分解为相似子问题的复杂问题,特别是在优化问题上表现出色,如最短路径、最大子数组和、编辑距离等。动态规划的核心思想是将原问题分解为较小的子…...
安装nodejs2011并配置npm仓库
1. 安装nodejs 选择2011版本下载 在安装目录(个人情况)下 D:\Program Files\nodejs2011创建2个文件夹: node_global (依赖库) node_cache (缓存) 然后在当前目录下cmd进入dos窗口,执行: npm c…...
排序C++代码(已更:快速排序,归并排序)
一、快速排序 #include<iostream> using namespace std;//设定三个数组,判断排序算法代码的正确性 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
正文共:1333 字 21 图,预估阅读时间:2 分钟 上次我们在Windows上尝试用Tesla M4配置深度学习环境(TensorFlow识别GPU难道就这么难吗?还是我的GPU有问题?),但是失败了。考虑到Windows…...
Java设计模式——策略
前言 策略模式是平时Java开发中常用的一种,虽然已有很多讲解设计模式的文章,但是这里还是写篇文章来从自己理解的角度讲解一下。 使用场景 我们不妨进行场景假设,要对我们的软件进行授权管理:在启动我们的软件之前先要校验是否…...
线性代数的本质 1 向量
向量是线性代数中最为基础的概念。 何为向量? 从物理上看, 向量就是既有大小又有方向的量,只要这两者一定,就可以在空间中随便移动。 从计算机应用的角度看,向量和列表很接近,可以用来描述某对象的几个不同…...
基于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篇】
🚀 作者 :“码上有前” 🚀 文章简介 :后端高频面试题 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬 后端高频面试题--Mybatis篇 什么是Mybatis?Mybatis的优缺点?Mybatis的特点…...
【笔记】Helm-5 Chart模板指南-12 .helmignore文件
.helmignore文件 .helmignore文件用来指定您不想包含在您的helm chart中的文件。 如果该文件存在,helm package命令会在打包应用时忽略所有在.helmignore文件中匹配的文件。 有助于避免不需要的或敏感文件及目录添加到您的helm chart中。 .helmignore文件支持Uni…...
【MySQL】表的增删改查(基础)
MySQL表的增删改查(基础) 1. CRUD2. 新增(Create)2.1 单行数据全列插入2.2 多行数据 指定列插入 3. 查询(Retrieve)3.1 全列查询3.2 指定列查询3.3 查询字段为表达式3.4 别名3.5 去重:DISTINCT…...
Android矩阵Matrix动画缩放Bitmap移动手指触点到ImageView中心位置,Kotlin
Android矩阵Matrix动画缩放Bitmap移动手指触点到ImageView中心位置,Kotlin 借鉴 Android双指缩放ScaleGestureDetector检测放大因子大图移动到双指中心点ImageView区域中心,Kotlin(2)-CSDN博客 在此基础上实现手指在屏幕上点击后&…...
C语言:表达式求值
引言:在笔试中,有一类的题目,题目给出代码,要求分析得出输出结果。这类题目更加考察我们对于运算顺序和运算类型转换的理解。文章介绍了隐式类型转换和操作符注意点,希望增加读者对于表达式求值的理解。 1.隐式类型转…...
GO 的 Web 开发系列(五)—— 使用 Swagger 生成一份好看的接口文档
经过前面的文章,已经完成了 Web 系统基础功能的搭建,也实现了 API 接口、HTML 模板渲染等功能。接下来要做的就是使用 Swagger 工具,为这些 Api 接口生成一份好看的接口文档。 一、写注释 注释是 Swagger 的灵魂,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 实战源码地址,一键下载可用…...
我为什么选择Xamarin开发ios app安卓app
临岁之寒简书作者,转载 Xamarin是一项跨平台开发技术,之前是收费的,而且据说收费不菲,所以使用的人数比较少,在国内几乎无人问津。后来Xamarin被微软收购,现已免费开放,相信今后国内的使用人群会大幅地增长…...
安全基础~通用漏洞4
文章目录 知识补充XSS跨站脚本**原理****攻击类型**XSS-后台植入Cookie&表单劫持XSS-Flash钓鱼配合MSF捆绑上线ctfshow XSS靶场练习 知识补充 SQL注入小迪讲解 文件上传小迪讲解 文件上传中间件解析 XSS跨站脚本 xss平台: https://xss.pt/ 原理 恶意攻击者…...
2024/2/12 图的基础知识 2
目录 查找文献 P5318 【深基18.例3】查找文献 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 有向图的拓扑序列 848. 有向图的拓扑序列 - AcWing题库 最大食物链计数 P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 查找文献 P5318 【深基18.例3】…...
无人机飞行原理,多旋翼无人机飞行原理详解
多旋翼无人机升空飞行的首要条件是动力,有了动力才能驱动旋粪旋转,才能产生克服重力所必需的升力。使旋翼产生升力,进而推动多旋翼无人机升空飞行的一套设备装置称为动力装置,包括多旋翼无人机的发动机以及保证发动机正常工作所必…...
docker本地目录挂载
小命令 1、查看容器详情 docker inspect 容器名称 还是以nginx为例,上篇文章我们制作了nginx静态目录的数据卷,此时查看nginx容器时会展示出来(docker inspect nginx 展示信息太多,这里只截图数据卷挂载信息)&#…...
使用C++从零开始,自己写一个MiniWeb
第一步:新建项目 1、打开VS点击创建新项目 2、选择空项目并点下一步(切记不能选错项目类型) 3、填写项目名称和路径,点击创建即可 新建好后项目是这样的比较干净 4、右击源文件,点击添加,新建http.cpp文件…...
Android Graphics 图像显示系统 - 开篇
“ 随着学习的不断深入和工作经验的积累,欲将之前在博客中整理的Android Graphics知识做进一步整理,并纠正一些理解上的错误,故开设Graphics主题系列文章 ” 序言 由于工作需要,也源于个人兴趣,终于下决心花时间整理一…...
机器学习在各个行业的应用介绍
随着科技的飞速发展,机器学习已经从实验室走向了现实世界,逐渐成为各行各业不可或缺的工具。从金融领域到医疗健康,从零售市场到制造业,机器学习正在改变着我们的工作方式和生活质量。 本文将深入探讨机器学习在以下几个领域的应用…...
【生产实测有效】Windows命令行查看激活状态脚本
Windows查看激活状态关键代码 通过windows server 自带的PowerShell来执行 Get-WmiObject SoftwareLicensingProduct | Select-Object -Property Description, LicenseStatus | findstr "Operating System"|findstr "1$"Get-WmiObject SoftwareLicensingPr…...
简单的Udp服务器
目录 简单的UDP网络程序1.1 UdpServer.hpp1.2 UdpClient.cc1.3 main.cc1.4 makefile1.5 log.hpp 简单的UDP网络程序 1.1 UdpServer.hpp #pragma once#include <iostream> using namespace std;#include <unistd.h> #include <sys/types.h> #include <sy…...
【Linux进程间通信】用管道实现简单的进程池、命名管道
【Linux进程间通信】用管道实现简单的进程池、命名管道 目录 【Linux进程间通信】用管道实现简单的进程池、命名管道为什么要实现进程池?代码实现命名管道创建一个命名管道 理解命名管道匿名管道与命名管道的区别命名管道的打开规则 作者:爱写代码的刚子…...
Linux操作系统基础(九):Linux用户与权限
文章目录 Linux用户与权限 一、文件权限概述 二、终端命令:组管理 三、终端命令:用户管理 1、创建用户 、 设置密码 、删除用户 2、查看用户信息 3、su切换用户 4、sudo 4.1、给指定用户授予权限 4.2、使用 用户 zhangsan登录, 操作管理员命令…...
蓝桥杯——第 5 场 小白入门赛(c++详解!!!)
文章目录 1 十二生肖基本思路: 2 欢迎参加福建省大学生程序设计竞赛基本思路:代码: 3 匹配二元组的数量基本思路:代码: 4 元素交换基本思路:代码: 5 下棋的贝贝基本思路:代码: 6 方程…...
Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现)
文章目录 题面链接题意题解代码总结 题面 链接 C. Kefa and Park 题意 求叶节点数量,叶节点满足,从根节点到叶节点的路径上最长连续1的长度小于m 题解 这道题目主要是实现,当不满足条件时直接返回。 到达叶节点后统计答案,用…...
797. 差分
Problem: 797. 差分 文章目录 思路解题方法复杂度Code 思路 这是一个差分数组的问题。差分数组的主要适用场景是频繁对原始数组的某一个区间进行增减操作。这种操作是区间修改操作,在这种操作下,差分数组只需要对区间的两个端点进行操作,时间…...
2024.2.5 vscode连不上虚拟机,始终waiting for server log
昨天还好好的,吃着火锅,做着毕设,突然就被vscode给劫了。 起初,哥们跟着网上教程有模有样地删除了安装包缓存,还删除了.vscode-server,发现没卵用,之前都是搜那个弹窗报错。 后来发现原来是vsco…...
CSS基础---新手入门级详解
CSS:层叠样式表 CSS(Cascading Style Sheets,层叠样式表),是一种用来为结构化文档添加样式(字体、间距和颜色)的计算机语言,css扩展名为.css。 实例: <!DOCTYPE html><html> <head><…...
Python中Pymysql库的常见用法和代码示例
关注B站可以观看更多实战教学视频:肆十二-的个人空间-肆十二-个人主页-哔哩哔哩视频 (bilibili.com) pymysql是一个用于连接MySQL数据库的Python库,它允许你执行SQL查询并处理返回的结果。以下是pymysql库的一些常见用法和代码示例: 1. 安装…...
使用 WPF + Chrome 内核实现高稳定性的在线客服系统复合应用程序
对于在线客服与营销系统,客服端指的是后台提供服务的客服或营销人员,他们使用客服程序在后台观察网站的被访情况,开展营销活动或提供客户服务。在本篇文章中,我将详细介绍如何通过 WPF Chrome 内核的方式实现复合客服端应用程序。…...
fastapi mysql 开发restful 3
pip install mysql-connector-python pymysql 数据库链接 创建src目录,里面创建db.py 代码如下: # 导入mysql.connector模块,该模块提供了与MySQL数据库进行连接和交互的功能。 import mysql.connector # 定义一个函数get_db_connectio…...
【Uniapp uni-app学习与快速上手——详细讲解】
Uniapp uni-app学习与快速上手——详细讲解 1. 介绍2. Uni-app 学习资源3. 快速上手4. 开始第一个项目5. 调试和发布 1. 介绍 Uni-app 是一个使用 Vue.js 编写多端应用的前端框架。开发者可以编写一份代码,然后发布到iOS、Android、网页(响应式…...
剑指offer——旋转数组的最小数字
目录 1. 题目描述2. 分析思路2.1 示例分析 3. 更完美的做法 1. 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3.4,5,1.2}为{1.2,3,4,5}的一个旋转&a…...
盘点数据可视化大屏焦点图十种样式
所谓焦点图就是大屏中居于中心位置的图,是视觉的中心,本位列举了十种焦点图样式供大家参考。 地球作为焦点图 图片来自网络 地图作为焦点图 图片来自网络 城市作为焦点图 图片来自网络 园区做焦点图 图片来自网络 建筑做焦点图 图片来自网络 生产线…...
问题 G: 老鼠和猫的交易
题目描述 小老鼠准备了M磅的猫粮,准备去和看守仓库的猫做交易,因为仓库里有小老鼠喜欢吃的五香豆。 仓库有N个房间; 第i个房间有J[i] 磅的五香豆,并且需要用F[i]磅的猫粮去交换; 老鼠不必交换该房间所有的五香豆&…...
HiveSQL——借助聚合函数与case when行转列
一、条件函数 if 条件函数 if函数是最常用到的条件函数,其写法是if(xn,a,b), xn代表判断条件,如果xn时,那么结果返回a ,否则返回b。 selectif(age < 25 or age is null, 25岁以下, 25岁以上) as age_cnt,count(1) as number from table…...
冒泡排序,判断回文,以及12-24小时制
6-7 定义函数,完成冒泡排序算法。 本题定义一个冒泡排序算法的函数,调用函数后实现数组的升序排序,其数组长度为任意长度。 函数接口定义: 在这里描述函数接口。例如: void sort(int arr[],int n); 在这里解释接口…...
【Vue】computed与watch
📝个人主页:五敷有你 🔥系列专栏:Vue⛺️稳重求进,晒太阳 计算属性 概念:基于现有的数据,计算出来新的属性,依赖的数据变化,自动重新计算 语法: 声明…...
探索设计模式的魅力:捕捉变化的风-用观察者模式提升用户体验
设计模式专栏:http://t.csdnimg.cn/U54zu 目录 一、引言 核心概念 应用场景 可以解决的问题 二、场景案例 2.1 不用设计模式实现 2.2 存在问题 2.3 使用设计模式实现 2.4 成功克服 三、工作原理 3.1 结构图和说明 3.2 工作原理详解 3.3 实现步骤 四、 优…...
SpringCloud-高级篇(十九)
我们已经学过使用 SpringAMQP去收和发消息,但是发和收消息是只是MQ最基本的功能了,在收发消息的过程中,会有很多的问题需要去解决,下面需要学习rabbitMQ的高级特性去解决 死信交换机:这个可以帮助我们实现消息的延迟的…...
Junit常用断言
0.断言简介 断言:assert Q:断言的作用 更方便的对结果进行判定 "有针对性"的if判断 针对两个变量值是否相同 使用assertEquals针对两个对象是否相同 使用assertSame针对返回值是否为True 使用assertTrue 1.断言的参数 assertXXX(”断言失败时提升的信息“&#x…...
docker 实现 mysql:8.3.0 主从复制(2024年2月13日最新版本)
环境为 CentOS 7.6, 具体操作请看MySQL主从复制01-主从复制概述及原理_哔哩哔哩_bilibili 1、配置主服务器 # 启动主服务器 docker run -p 3306:3306 --name mysql_master -e MYSQL_ROOT_PASSWORDnmnmnm67890890 -v /docker/mysql_master/conf:/etc/mysql/conf.d…...
STM32 + ESP8266,连接阿里云 上报/订阅数据
(文章正在编辑中,一点点地截图操作过程,估计要拖拉两三天) 一、烧录MQTT固件 ESP8266出厂时,默认是AT固件。连接阿里云,需要使用MQTT固件。 1、独立EPS8266模块的烧录方法 2、魔女开发板,板载…...
如何利用chatgpt提升工作效率?
在数字化和信息化的时代,人工智能技术已经深入到了我们生活的方方面面。其中,ChatGPT作为当前热门的人工智能技术,以其强大的自然语言处理能力和广泛的应用场景,正逐渐改变着我们的工作方式,为我们提高工作效率提供了全…...
MongoDB聚合:$geoNear
$geoNear根据指定的点按照距离以由近到远的顺序输出文档。 从4.2版本开始,MongoDB移除了limit和num选项以及100个文档的限制,如果要限制结果文档的数量可以使用$limit阶段。 语法 { $geoNear: { <geoNear options> } }$geoNear操作接受一个包含…...
Docker-CE 国内源国内镜像
Docker-CE 就是 Docker Community Edition 的意思 docker-ce由docker官方维护 , docker.io由Debian维护 Docker官文 – Install Docker Engine on CentOS Docker官文 – Install Docker Engine on Fedora Docker官文 – Install Docker Engine on Debian Docker官文 – In…...
【Tauri】(3):使用Tauri1.5版本,进行桌面应用开发,在windows上搭建环境,安装node,rust环境,可以打包成功,使用vite创建应用
1,视频地址: https://www.bilibili.com/video/BV1Ny421a7nA/ 【Tauri】(3):使用Tauri1.5版本,进行桌面应用开发,在windows上搭建环境,安装node,rust环境,可以…...