DP:子序列问题

文章目录

  • 什么是子序列
    • 子序列的特点
    • 举例说明
    • 常见问题
  • 关于子序列问题的几个例题
    • 1.最长递增子序列
    • 2.摆动序列
    • 3.最长递增子序列的个数
    • 4.最长数对链
    • 5.最长定差子序列
  • 总结

在这里插入图片描述

什么是子序列

在计算机科学和数学中,子序列(Subsequence)是指从一个序列中删除一些元素(可以是零个或多个),但不改变其余元素相对顺序后形成的新序列。

子序列的特点

元素的相对顺序保持不变。
可以删除零个或多个元素。
一个序列的子序列可以为空序列,即不包含任何元素。

举例说明

设有序列 S = [A, B, C, D, E],则其子序列可以有:
删除零个元素:[A, B, C, D, E](即自身)
删除一个元素:[A, B, C, D]、[A, B, C, E]、[A, B, D, E]、[A, C, D, E]、[B, C, D, E]
删除两个元素:[A, B, C]、[A, B, D]、[A, B, E]、[A, C, D]、[A, C, E]、[A, D, E]、[B, C, D]、[B, C, E]、[B, D, E]、[C, D, E]
删除三个元素:[A, B]、[A, C]、[A, D]、[A, E]、[B, C]、[B, D]、[B, E]、[C, D]、[C, E]、[D, E]
删除四个元素:[A]、[B]、[C]、[D]、[E]
删除所有元素:[](空序列)

常见问题

子序列问题在算法设计和编程竞赛中非常常见。以下是几种经典问题:
最长公共子序列(LCS):给定两个序列,找出它们的最长公共子序列。动态规划是解决这个问题的常用方法。
最长递增子序列(LIS):给定一个序列,找出其中最长的递增子序列。可以使用动态规划或贪心算法结合二分查找解决。
子序列和问题:给定一个序列,找出所有和为特定值的子序列。可以使用回溯法或动态规划解决。

根据我上面的介绍,可以总结,大多数子序列问题其实都可以用DP的算法来解决。

关于子序列问题的几个例题

1.最长递增子序列

题目链接
题目:

在这里插入图片描述

样例 输出和输入:

在这里插入图片描述

首先根据上述子序列的描述,这道题就很容易理解了,就是 让我们求给定数组的最长的递增子序列。
算法原理:
状态表示:dp[i]表示以i位置为结尾的所有子序列中最长的那个子序列的长度。
状态转移方程:
在这里插入图片描述
首先我们要求状态转移方程就要看i位置的状态,我们要确定i位置的状态,是不是应该将0到i-1位置遍历一遍,然后将当中的最长子序列求出来然后再加上当前位置的长度1就可以了,这是当子序列长度大于1的时候,还有一种情况是长度等于1的时候,长度等于1的时候,可以默认看做一个子序列,所以dp[i]就等于1,当长度大于1的时候,这种情况,我们先用一个变量j将0到i-1位置的最长子序列遍历出来,然后再+1,所以状态转移方程:dp[i] = max(dp[j]+1,dp[i])
初始化:因为单独一个元素就可以看做一个递增的子序列,所以DP表中的值可以全部初始化为1.
代码展示:

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n,1);int dpmax = 1;for (int i = 1;i < n;i++){for (int j = i-1;j >= 0;j--){if (nums[j] < nums[i]){dp[i] = max(dp[j]+1,dp[i]);}dpmax=max(dp[i],dpmax);}}return dpmax;}
};

运行结果:
在这里插入图片描述

2.摆动序列

题目链接
题目:

在这里插入图片描述

样例 输出和输入:

在这里插入图片描述

这道题让我们求摆动序列的最长的子序列的长度,首先我们要搞清楚,什么是摆动序列:
在这里插入图片描述

上面就是一个摆动序列。
算法原理:
这道题首先要求摆动序列,我们上个专题已经做过类似的题了,就像湍流数组一样,这道题很显然,我们需要两个状态,一个状态是向下的状态,一个状态是向上的状态,这里定义f[i]是向上的状态,g[i]是向下的状态。
状态表示:f[i]是以i位置为结尾的子序列中长度最长且最后一个状态是向上的最长子序列的长度,g[i]表示以i位置为结尾最后的子序列中最后一个状态向下的最长子序列的长度。
状态转移方程:首先对f[i]分析:在这里插入图片描述
所以这里f[i]的状态转移方程:f[i] = max(g[j] + 1, f[i]),同理也可以求出g[i]的状态转移方程:g[i] = max(f[j] + 1, g[i])
代码展示:

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();vector<int> f(n,1), g(n,1);int dpmax = 1;for (int i = 1;i < n;i++){for (int j = i - 1;j >= 0;j--){if (nums[j] > nums[i]){g[i] = max(f[j] + 1, g[i]);}else if (nums[j] < nums[i]){f[i] = max(g[j] + 1, f[i]);}dpmax = max(max(dpmax, f[i]), g[i]);}}return dpmax;}
};

运行结果:
在这里插入图片描述

3.最长递增子序列的个数

题目链接
题目:

在这里插入图片描述

样例 输出和输入:

在这里插入图片描述

这道题相对于第一道题换了一个问法。这道题是求最长子序列的个数
算法原理:
状态表示:首先我们先定义一个状态,看这个状态能推下去吗,dp[i]表示以i位置为结尾的所有子序列中,最长子序列的个数。
状态转移方程:首先这里就出问题了 ,这里我们根本不知道最长的子序列是什么,因为根本没有记录的,所以这里根本就推不出来,所以还得加一个len[i],len[i]表示以i位置为结尾的所有子序列中最长子序列的长度,将dp[i]改为count[i],count[i]表示以i位置为结尾的所有子序列中最长的子序列的个数。接下来来推状态转移方程,在这里插入图片描述
有三种情况,当我们遍历的len[j]+1==len[i],意思就是0到i-1位置的子序列中加上当前的长度和之前的最长的子序列是相同的,这里我们应该把以j位置为结尾的最长子序列的个数全部加到count[i]]中。这里画图表示
在这里插入图片描述

根据这些情况可以将表填完,但是,我们还需要 一个retlen和一个retcount更新每次的最长子序列的长度和最长子序列的个数。
这里也分为三种情况,和上面的情况相同,只需要每次遍历完一个位置,更新结果即可。

代码展示:

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n = nums.size();vector<int> len(n,1), count(n,1);//统计每次的每次的最终结果int retlen = 1, retcount = 1;for (int i = 1;i < n;i++){for (int j = i - 1;j >= 0;j--){//当出现递增的时候if (nums[j] < nums[i]){//判断如果加上递增的那一个和当前最长的长度还是一样的则需要更新countif (len[j] + 1 == len[i])count[i] += count[j];//如果加上当前的一个元素比比之前的最长的子序列要长,则重新规划长度else if (len[j] + 1 > len[i])count[i] = count[j],len[i] = len[j];}}//统计每次的结果,如果len和结果的len相同,则直接用count累加if (retlen == len[i])retcount += count[i];//如果len比结果的len要大,则直接重置结果len和结果的countelse if (retlen < len[i])retcount = count[i], retlen = len[i];}return retcount;}
};

运行结果:
在这里插入图片描述

4.最长数对链

题目链接
题目:

在这里插入图片描述

样例 输出和输入:

在这里插入图片描述

这道题其实和求最长子序列的长度是相同的题,但是换了一个形式而已,根据题目条件我们可以得知什么是数对链:
在这里插入图片描述
数对连就要满足上述条件
算法原理:
预处理:首先我们得将数组排序,排序的规则,只需要比较每个数对的第一个元素的大小即可,因为每个数对都是单增的,如果我们排序之后保证了a>c,那么d>c是绝对大于前一个数对的,所以这里只需要根据前一个数排序即可。
状态表示:这里dp[i]表示以i位置为结尾的所有数对链中最长的那个数对链的长度。
状态转移方程:分两种情况:
在这里插入图片描述

代码展示:

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(), pairs.end());int n = pairs.size();vector<int> dp(n, 1);int ret = 1;for (int i = 1;i < n;i++){for (int j = i - 1;j >= 0;j--){if (pairs[j][1] < pairs[i][0]){dp[i] = max(dp[j] + 1, dp[i]);}ret = max(dp[i], ret);}}return ret;}
};

运行结果:
在这里插入图片描述

5.最长定差子序列

题目链接
题目:

在这里插入图片描述

样例 输出和输入:

在这里插入图片描述

这道题给定一个difference,让我们求出数组中的差为difference的最长的子序列的长度
算法原理:
状态表示:dp[i]表示以i位置为结尾的所有子序列中的最长的等差子序列,且差值是difference。
状态转移方程:首先我们可以分析一下,我们可以选择从0位置开始遍历寻找和i位置之差是difference的数,这里的dp表其实我们可以借助hash表来充当,因为每次我们都得去前面找和i位置差值是difference的数,所以这里hash表既可以充当dp表,也可以将前一个位置和当前位置的差值是difference的数存起来。
这里的状态转移方程:hash[arr[i]] = hash[arr[i] - difference] + 1这里如果没有在hash表中找到前一个位置差值是difference值的数,则hash[arr[i] - difference]就是0,所以也免去了这种情况,由于我们找的是离i位置最近的前一个位置,这里也可以用hash表解决,因为,我们是从左到右遍历的,这就使得后一个位置每次都是覆盖了前一个位置的值,每次都是最新的状态值。

代码展示:

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int, int> hash;//arr[i]----dp[i]hash[arr[0]] = 1;int ret = 1;for (int i = 1;i < arr.size();i++){//需要的最后一个b的值,这个hash能保证,因为从左到右遍历,前面的值已经被覆盖了hash[arr[i]] = hash[arr[i] - difference] + 1;ret = max(ret, hash[arr[i]]);}return ret;}
};

运行结果:

在这里插入图片描述

总结

通过本文对子序列问题的探讨,我们深入理解了动态规划在解决此类问题中的重要性。无论是经典的最长公共子序列(LCS)问题,还是最长递增子序列(LIS)问题,动态规划都展示了其强大的解题能力。通过将问题分解为更小的子问题,并记录这些子问题的解,我们能够高效地找到最优解,避免重复计算。

此外,我们还见识了动态规划解决子序列问题的多种变体及其实际应用。这不仅拓宽了我们对算法设计的视野,也提升了我们在面对复杂问题时的解决能力。子序列问题不仅在理论上具有重要意义,也在现实世界中的许多领域,如生物信息学、文本处理和数据分析中有着广泛的应用。

希望通过本文的讲解,读者能对动态规划在子序列问题中的应用有更深的理解,并能将这些技术应用于实际编程中,解决更多实际问题。动态规划的学习不仅仅局限于特定问题,更是培养一种思维方式,一种解决复杂问题的系统方法。愿大家在未来的算法学习和应用中继续精进,取得更大的进步。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/366748.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【JavaEE精炼宝库】多线程进阶(2)synchronized原理、JUC类——深度理解多线程编程

一、synchronized 原理 1.1 基本特点&#xff1a; 结合上面的锁策略&#xff0c;我们就可以总结出&#xff0c;synchronized 具有以下特性(只考虑 JDK 1.8)&#xff1a; 开始时是乐观锁&#xff0c;如果锁冲突频繁&#xff0c;就转换为悲观锁。 开始是轻量级锁实现&#xff…

维护Nginx千字经验总结

Hello , 我是恒 。 维护putty和nginx两个项目好久了&#xff0c;用面向底层的思路去接触 在nginx社区的收获不少&#xff0c;在这里谈谈我的感悟 Nginx的夺冠不是偶然 高速:一方面&#xff0c;在正常情况下&#xff0c;单次请求会得到更快的响应&#xff1b;另一方面&#xff0…

Linux:网络基础1

文章目录 前言1. 协议1.1 为什么要有协议&#xff1f;1.2 什么是协议&#xff1f; 2. 网络2.1 网络通信的问题2.2 网络的解决方案——网络的层状结构2.3 网络和系统的关系2.4 网络传输基本流程2.5 简单理解IP地址2.6 跨网络传输 总结 前言 在早期的计算机发展中&#xff0c;一开…

免费翻译API及使用指南——百度、腾讯

目录 一、百度翻译API 二、腾讯翻译API 一、百度翻译API 百度翻译API接口免费翻译额度&#xff1a;标准版&#xff08;5万字符免费/每月&#xff09;、高级版&#xff08;100万字符免费/每月-需个人认证&#xff0c;基本都能通过&#xff09;、尊享版&#xff08;200万字符免…

Linux驱动开发实战宝典:设备模型、模块编程、I2C/SPI/USB外设精讲

摘要: 本文将带你走进 Linux 驱动开发的世界,从设备驱动模型、内核模块开发基础开始,逐步深入 I2C、SPI、USB 等常用外设的驱动编写,结合实际案例,助你掌握 Linux 驱动开发技能。 关键词: Linux 驱动,设备驱动模型,内核模块,I2C,SPI,USB 一、Linux 设备驱动模型 Li…

cesium 聚合

cesium 聚合(下面附有源码) 示例代码 <html lang="en"><head><!-- Use correct character set. -->

python系列30:各种爬虫技术总结

1. 使用requests获取网页内容 以巴鲁夫产品为例&#xff0c;可以用get请求获取内容&#xff1a; https://www.balluff.com.cn/zh-cn/products/BES02YF 对应的网页为&#xff1a; 使用简单方法进行解析即可 import requests r BES02YF res requests.get("https://www.…

JSON JOLT常用示例整理

JSON JOLT常用示例整理 1、什么是jolt Jolt是用Java编写的JSON到JSON转换库&#xff0c;其中指示如何转换的"specification"本身就是一个JSON文档。以下文档中&#xff0c;我统一以 Spec 代替如何转换的"specification"json文档。以LHS(left hand side)代…

云计算基础技术

网络类技术 网络的作用 网络是设备间、虚拟机之间通信的桥梁。因此&#xff0c;在ICT基础设施中&#xff0c;网络是必不可少的。 传统网络的基本概念 广播和单播&#xff1a;两个设备通信就好像是人们之间的对话一样。如果一个人对另外一个人说话&#xff0c;那么用网络技术的…

从零开始搭建spring boot多模块项目

一、搭建父级模块 1、打开idea,选择file–new–project 2、选择Spring Initializr,选择相关java版本,点击“Next” 3、填写父级模块信息 选择/填写group、artifact、type、language、packaging(后面需要修改)、java version(后面需要修改成和第2步中版本一致)。点击“…

容器内存

一、容器内存概述 容器本质上还是一个进程&#xff0c;是一个被隔离和限制的进程。因此容器内存和进程内存在表现形式上其实是一样的&#xff0c;这块主要涉及三部分内容&#xff1a;RSS&#xff0c;page cache和swap这三部分&#xff0c;容器基于memory Cgroup对内存进行限制…

HSRP热备份路由协议(VRRP虚拟路由冗余协议)配置以及实现负载均衡

1、相关原理 在网络中&#xff0c;如果一台作为默认网关的三层交换机或者路由器损坏&#xff0c;所有使用该网关为下一跳的主机通信必然中断&#xff0c;即使配置多个默认网关&#xff0c;在不重启终端的情况下&#xff0c;也不能彻底换到新网关。Cisco提出了HSRP热备份路由协…

Paragon NTFS与Tuxera NTFS有何区别 Mac NTFS 磁盘读写工具选哪个好

macOS系统虽然以稳定、安全系数高等优点著称&#xff0c;但因其封闭性&#xff0c;不能对NTFS格式磁盘写入数据常被人们诟病。优质的解决方案是使用磁盘管理软件Paragon NTFS for Mac&#xff08;点击获取激活码&#xff09;和Tuxera NTFS&#xff08;点击获取激活码&#xff0…

消防认证-防火卷帘

一、消防认证 消防认证是指消防产品符合国家相关技术要求和标准&#xff0c;且通过了国家认证认可监督管理委员会审批&#xff0c;获得消防认证资质的认证机构颁发的证书&#xff0c;消防产品具有完好的防火功能&#xff0c;是住房和城乡建设领域验收的重要指标。 二、认证依据…

springboot学习,如何用redission实现分布式锁

目录 一、springboot框架介绍二、redission是什么三、什么是分布式锁四、如何用redission实现分布式锁 一、springboot框架介绍 Spring Boot是一个开源的Java框架&#xff0c;由Pivotal团队&#xff08;现为VMware的一部分&#xff09;于2013年推出。它旨在简化Spring应用程序…

C# 警告 warning MSB3884: 无法找到规则集文件“MinimumRecommendedRules.ruleset”

警告 warning MSB3884: 无法找到规则集文件“MinimumRecommendedRules.ruleset” C:\Program Files\Microsoft Visual Studio\2022\Professional\MSBuild\Current\Bin\amd64\Microsoft.CSharp.CurrentVersion.targets(129,9): warning MSB3884: 无法找到规则集文件“MinimumRe…

SpringMVC的基本使用

SpringMVC简介 SpringMVC是Spring提供的一套建立在Servlet基础上&#xff0c;基于MVC模式的web解决方案 SpringMVC核心组件 DispatcherServlet&#xff1a;前置控制器&#xff0c;来自客户端的所有请求都经由DispatcherServlet进行处理和分发Handler&#xff1a;处理器&…

【观察】戴尔科技+AMD:释放技术创新“乘数效应”,助力制造业打造“新质生产力”...

在今年的政府工作报告中&#xff0c;“人工智能”首次被写入报告&#xff0c;同时“大力推进现代化产业体系建设&#xff0c;加快发展新质生产力”也被列为2024年的首项政府工作任务&#xff0c;其重要性不言而喻。 尤其是最近几年&#xff0c;以人工智能、大模型、大数据、云计…

成人职场商务英语学习柯桥外语学校|邮件中的“备注”用英语怎么说?

在英语中&#xff0c;"备注"通常可以翻译为"Notes" 或 "Remarks"。 这两个词在邮件中都很常用。例如: 1. Notes Notes: 是最通用和最常见的表达&#xff0c;可以用在各种情况下&#xff0c;例如&#xff1a; 提供有关电子邮件内容的附加信息 列…

深入解析 androidx.databinding.Bindable 注解

在现代 Android 开发中&#xff0c;数据绑定 (Data Binding) 是一个非常重要的技术。它使得我们能够简化 UI 和业务逻辑之间的连接&#xff0c;从而提高代码的可读性和维护性。在数据绑定中&#xff0c;Bindable 注解是一个关键部分&#xff0c;它帮助我们实现双向数据绑定和自…