DP:子序列模型

子数组vs子数列

1、子数组(n^2)    子序列(2^n)       

2、子数组是子序列的一个子集

3、子数组必须连续,子序列可以不连续

一、最长递增子序列

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i]表示以i位置为结尾所有子系列中,最长递增子序列的长度。 

 2、状态转移方程

(1)长度为1——>dp[i]=1

  (2)   长度大于1——>满足前提(nums[j]<nums[i])——>max(dp[j]+1,dp[i])  (0<=j<=i-1)

3、初始化

如果无法更新,最差情况自己也是一个子序列,所以dp表全都初始化为1

4、填表顺序

需要借助前面的状态,所以要从左往右

5、返回值

dp表中的最大值——>可以用ret去更新出最大值,也可以用*max_element(dp.begin(),dp.end())

6、复杂度

时间复杂度:N^2 (因为是子序列而非子数组,所以当我们固定住i的时候,他的前面可以是i-1、i-2、i-3…… 所以需要遍历一遍更新出最大的长度)

空间复杂度:N

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
         int n=nums.size();
         vector<int> dp(n,1);
         for(int i=1;i<n;++i)
           for(int j=0;j<i;++j)
              if(nums[j]<nums[i]) dp[i]=max(dp[j]+1,dp[i]); //前提条件要满足
         return *max_element(dp.begin(),dp.end());//dp数组中的最大值
    }
};

二、摆动序列

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i]表示以i位置为结尾所有子序列中,最长递增子序列的长度。 (错误)

因为会存在两种状态,所以我们需要两个dp数组:

f[i]表示以i位置为结尾的所有子序列中,最后一个位置呈现“上升”趋势的最长摆动序列的长度

g[i]表示以i位置为结尾的所有子序列中,最后一个位置呈现“下降”趋势的最长摆动序列的长度

 2、状态转移方程

f[i](上升):

(1)长度为1——>1

  (2)   长度大于1——>满足前提(nums[j]<nums[i])——>max(g[j]+1,f[i])  (0<=j<=i-1)

g[i](下降):

(1)长度为1——>1

  (2)   长度大于1——>满足前提(nums[j]>nums[i])——>max(f[j]+1,g[i])  (0<=j<=i-1)

3、初始化

如果无法更新,最差情况自己也是一个子序列,所以g表和f表全都初始化为1

4、填表顺序

需要借助前面的状态,所以要从左往右,两个表一起填

5、返回值

两个表中的最大值

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        //f[i]表示以i位置结尾的最长子序列中,最后呈现上升趋势 (前提nums[i]<nums[j])
        //g[i]表示以i位置结尾的最长子序列中,最后成下降趋势    (前提nums[i]>nums[j])
        int n=nums.size();
        vector<int> f(n,1),g(n,1);
        for(int i=1;i<n;++i)
           for(int j=0;j<i;++j)
                if(nums[i]<nums[j])  g[i]=max(f[j]+1,g[i]);
                else if(nums[i]>nums[j]) f[i]=max(g[j]+1,f[i]);
        return max(*max_element(f.begin(),f.end()),*max_element(g.begin(),g.end()));
    }
};

三、最长递增子序列的个数

. - 力扣(LeetCode)

在讲解前先来个小demo:如何在数组中找出最大值出现的次数

方案1:第一次for循环确定最大的值是多少,第二次for循环统计最大的值出现了几次

方案2:利用贪心策略一次for循环搞定(定义maxval记录当前的最大值,count统计数量)

(1)x==maxval:++count 

(2)x<maxval:直接无视

(3)x>maxval:更新最大值——>maxval=x,然后重新计数——>count=1

算法原理:

1、状态表示(经验+题目要求)

dp[i]表示以i位置为结尾所有子序列中,最长递增子序列的个数。 (错误)

因为我们在填表的时候并不能确认最长递增子序列的长度是多少,所以无法直接统计。我们就得用demo中的方案2的思想,来解决这个问题。

len[i]表示以i位置为结尾的所有子序列中,最长递增子序列的“长度”

count[i]表示以i位置为结尾的所有子序列中,最长递增子序列的“个数”

 2、状态转移方程

nums[j]<nums[i]时

(1)len[j]+1==len[i]——>count[i]+=count[j]

(2)len[j]+1<len[i] 无视

(3)len[j]+1>len[i]——>len[i]=len[j]+1  count[i]=count[j](更新最大值并重新计数)

3、初始化

全都初始化为1

4、填表顺序

需要借助前面的状态,所以要从左往右,两个表一起填

5、返回值

recount统计结果

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
         vector<int> len(n,1),count(n,1); //count统计以i位置结尾时最长子序列的个数 len是长度
         int retlen=1,recount=1;//统计最大长度和最大长度的个数
         for(int i=1;i<n;++i)
         {
           for(int j=0;j<i;++j)
             if(nums[i]>nums[j]) //构成子序列的前提条件
                if(len[j]+1==len[i])  count[i]+=count[j];
                else if(len[j]+1>len[i])len[i]=len[j]+1,count[i]=count[j];
             //更新一下最长长度和最大数
             
             if(retlen==len[i]) recount+=count[i];
             else if(retlen<len[i])
             {
                retlen=len[i];
                recount=count[i];
             }
         }
         return recount;
    }
};

四、最长数链对

. - 力扣(LeetCode)

算法原理:

预处理:由于题目要求是任意顺序组成数链对,所以我们在处理的时候不仅要考虑前面,还要考虑后面,这样不利于我们的动态规划表示,所以我们要先按照第一个元素进行排序(比如[a,b] [c,d],a<c<d 所以d>a,所以后面的不需要考虑到),我们要进行sort,在C++中,vector、pair的默认比较逻辑都是按照字典序的,恰好符合我们的要求,所以我们可以直接调用sort。

1、状态表示(经验+题目要求)

dp[i]表示以i位置为结尾所有数对链序列中,最长数对链的长度。 

 2、状态转移方程

dp[i]:

(1)长度为1——1

(2)长度大于1——p[j][1]>p[i][0] ——max(dp[i],dp[j]+1)

3、初始化

初始化为1

4、填表顺序

需要借助前面的状态,所以要从左往右

5、返回值

要返回dp表中的最大值,但由于我们排序过,所以最大值必然出现在dp[n-1]。

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        //vector的排序就像字典序一样
        //预处理直接sort 正好符合我们的要求
        sort(pairs.begin(),pairs.end());
        int n=pairs.size();
        vector<int> dp(n,1);
        for(int i=1;i<n;++i)
          for(int j=0;j<i;++j)
            if(pairs[j][1]<pairs[i][0]) dp[i]=max(dp[j]+1,dp[i]);//(1,5)(2,3)(4,10)(5,9)
        return dp[n-1];//最大值必然在最后面
    }
};

五、最长定差子序列(经典)

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i]表示以i位置为结尾所有子序列中,最长的等差子序列长度 

 2、状态转移方程

dp[i]:

(1)b不存在——>1

(2)b存在——>取最后一个即可dp[j]+1

我们会发现前一个数基本上是可以确定是多少的,并且有多个的话也可以用后面的覆盖前面的,因此我们可以用哈希表做优化

优化思路:

(1)将元素+dp[i]的值存在哈希表中

(2)直接在哈希表中做动态规划

3、初始化

hash[arr[0]]=1

4、填表顺序

从左往右

5、返回值

dp表里的最大值

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        //数据量太大了O(n^2)必然会超时
        int n=arr.size();
        unordered_map<int,int> hash;//第一个是元素,第二个是以这个元素为结尾时的最长等差子序列长度
        int ret=1;
        for(int&v:arr) //为了降低时间复杂度,我们发现这道题只需要最后的那个相同的
        {
            hash[v]=hash[v-difference]+1; //因为v-difference不在的时候,会被自己创建出来并初始化为0
            ret=max(ret,hash[v]);
        }
        return ret;
    }
};

    为什么哈希表不需要先将数组中的元素全部初始化为1???因为hash[v]=hash[v-difference]+1,当v-differences不存在的时候,重载方括号会去调用insert并允许我们修改second,在创建的时候初始化了。

六、最长的斐波那契子序列长度

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i]表示以i位置为结尾所有子序列中,最长的斐波那契子序列长度(错误)。

因为我们至少得确定两个位置,才能知道序列是否满足斐波那契子序列的要求。

dp[i][j]表示以i位置及j位置为结尾所有子序列中,最长的斐波那契子序列长度。

 2、状态转移方程

dp[i][j]:  (假设abc对应的坐标分别是kij)

(1)如果a存在且a<b——>dp[k][i]+1

(2)a存在且b<a<c——>2

(3)a不存在——>2

       我们固定两个数用了两层for循环了,如果找第三个数的时候还要在前面用一层for循环的话,那么就是n^3的时间复杂度了,所以我们可以用哈希表来帮助我们存储下标和元素的映射关系。并且我们只需要保存靠后的元素下标即可。

优化思路:将元素与下标绑定存放在哈希表中。

3、初始化

都初始化为2

4、填表顺序

从左往右

5、返回值

dp表里的最大值ret 但是如果ret是2的话就返回0

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) 
    {
         //必须通过元素快速找到dp表对应的下标 
         unordered_map<int,int> hash;//哈希帮助我们快速定位
         int n=arr.size();
         for(int i=0;i<n;++i) hash[arr[i]]=i;
         int ret=2;//起始为2
         vector<vector<int>> dp(n,vector<int>(n,2));//得知道两个位置,才能确定前面的
         for(int j=2;j<n;++j) //固定最后的位置
           for(int i=1;i<j;++i)//固定倒数第2个位置
            {
                int a=arr[j]-arr[i];
                if(hash.count(a)&&a<arr[i]) dp[i][j]=dp[hash[a]][i]+1;
                ret=max(dp[i][j],ret);
            }
        return ret==2?0:ret;
    }
};

七、最长等差数列

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i]表示以i位置为结尾所有子序列中,最长的等差子序列的长度(错误)。

因为我们至少得确定两个位置,才能知道序列是否满足等差子序列的要求。

dp[i][j]表示以i位置及j位置为结尾所有子序列中,最长的等差子序列长度。

 2、状态转移方程

dp[i][j]:  (假设abc对应的坐标分别是kij)

(1)如果a存在且a<b——>dp[k][i]+1

(2)a存在且b<a<c——>2

(3)a不存在——>2

       我们固定两个数用了两层for循环了,如果找第三个数的时候还要在前面用一层for循环的话,那么就是n^3的时间复杂度了,所以我们可以用哈希表来帮助我们存储下标和元素的映射关系。并且我们只需要保存靠后的元素下标即可。

优化思路:

(1)将元素与下标绑定存放在哈希表中。

(2)i位置填完后,将i位置的值放进哈希表中

3、初始化

都初始化为2

4、填表顺序

有两种方式(选择方法2

(1)先固定最后一个数,然后枚举倒数第二个数(必须在dp前先将元素与下标的关系绑定再哈希表中,到时候在找的时候还得判断b<a<c的情况)

(2)先固定倒数第二个数,再枚举最后一个数(可以等i位置填完后再将i的位置丢进哈希表,这样可以保证哈希表内的元素的下标必然是小的,就可以不需要判断b<a<c的情况)

5、返回值

dp表里的最大值ret

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
       //得确定至少两个位置,通过这两个位置求出了等差是多少,才能确定最终的结果
       unordered_map<int,int> hash;
       int n=nums.size();
       hash[nums[0]]=0;
       //必须要先固定两个数
       int ret=2;
       vector<vector<int>> dp(n,vector<int>(n,2));
       for(int i=1;i<n;++i) //边遍历边丢,这样就能确保哈希表里面的都是前面的元素
       {
         for(int j=i+1;j<n;++j)
         {
           int a=2*nums[i]-nums[j];
           if(hash.count(a)) dp[i][j]=dp[hash[a]][i]+1;
           ret=max(dp[i][j],ret);
         }
         hash[nums[i]]=i;//记住最后一个即可
       }
       return ret;
    }
};

八、等差数列划分II-子序列 

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i]表示以i位置为结尾所有子序列中,最长的等差子序列的长度(错误)。

因为我们至少得确定两个位置,才能知道序列是否满足等差子序列的要求。

dp[i][j]表示以i位置及j位置为结尾所有子序列中,最长的等差子序列长度。

 2、状态转移方程

dp[i][j]:  (假设abc对应的坐标分别是kij)

(1)如果a存在且a<b——>dp[i][j]+=dp[k][i]+1

(2)a存在且b<a<c——>0

(3)a不存在——>0

       我们固定两个数用了两层for循环了,如果找第三个数的时候还要在前面用一层for循环的话,那么就是n^3的时间复杂度了,所以我们可以用哈希表来帮助我们存储下标和元素的映射关系。并且我们只需要保存靠后的元素下标即可。

优化思路:

(1)将元素与下标绑定存放在哈希表中。(该题需要统计所有的子序列,所以相同元素下标不同的情况都要统计,因此我们要将元素绑定一个下标数组)

(2)i位置填完后,将i位置的值放进哈希表中

3、初始化

都初始化为0

4、填表顺序

       先固定倒数第二个数,再枚举最后一个数(可以等i位置填完后再将i的位置丢进哈希表,这样可以保证哈希表内的元素的下标必然是小的,就可以不需要判断b<a<c的情况)

5、返回值

dp表的总和——用一个sum去统计

 6、细节处理

可能会溢出,所以我们要下标要存储long

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用命令给电脑添加虚拟网卡和IP

目录 1、添加网卡 1-1、windows系统添加网卡 1-2、Linux系统中添加网卡 2、添加IP和DNS 2-1、添加IP 2-2、 设置DNS 3、删除网卡 3-1、Windows: 3-2、Linux 3-3、macOS 4、示例&#xff1a; 首先以管理员方式进入CMD命令行&#xff1b; 点击“开始”->“管理员…

HLA高层体系结构1.0.0版本

名&#xff1a;高层体系结构&#xff08;High Level Architecture&#xff0c;HLA&#xff09; 高层体系结构&#xff08;High Level Architecture&#xff0c;HLA&#xff09;是从体系结构上建立这样一个框架&#xff0c;它能尽量涵盖M&S领域中所涉及的各种不同类型的仿真…

springboot启动配置文件-bootstrap.yml常用基本配置

4.1.5.配置文件 SpringBoot的配置文件支持多环境配置&#xff0c;基于不同环境有不同配置文件&#xff1a; 说明&#xff1a; 文件说明bootstrap.yml通用配置属性&#xff0c;包含服务名、端口、日志等等各环境通用信息bootstrap-dev.yml线上开发环境配置属性&#xff0c;虚…

微服务开发与实战Day01 - MyBatisPlus

一、微服务 概念&#xff1a;微服务是一种软件架构风格&#xff0c;它是以专注于单一职责的很多小型项目为基础&#xff0c;组合除复杂的大型应用。 课程安排&#xff1a; https://www.bilibili.com/video/BV1S142197x7/?spm_id_from333.1007.top_right_bar_window_history.…

41【Aseprite 作图】粉红宫灯——拆解

1 宫灯轮廓 上面三角&#xff0c;下面3 3 3 &#xff08;粉色在后面&#xff0c;做轮廓&#xff09;&#xff0c;棕色在外面&#xff0c;看做是灯骨&#xff08;竖着更长&#xff09;&#xff1b;中间是横着做灯骨 尾部的彩带&#xff0c;下面粉色更浅&#xff0c;上面绿色更浅…

LabVIEW飞机发动机测试与故障诊断系统

LabVIEW飞机发动机测试与故障诊断系统 基于LabVIEW开发了一个飞机发动机测试与故障诊断系统&#xff0c;能够实时监测发动机的运行参数&#xff0c;进行数据采集与分析&#xff0c;并提供故障诊断功能。系统采用高精度传感器和数据采集硬件&#xff0c;适用于发动机的性能测试、…

Kaggle——Deep Learning(使用 TensorFlow 和 Keras 为结构化数据构建和训练神经网络)

1.单个神经元 创建一个具有1个线性单元的网络 #线性单元 from tensorflow import keras from tensorflow.keras import layers #创建一个具有1个线性单元的网络 modelkeras.Sequential([layers.Dense(units1,input_shape[3]) ]) 2.深度神经网络 构建序列模型 #构建序列模型 …

在k8s中部署Logstash多节点示例(超详细讲解)

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《洞察之眼&#xff1a;ELK监控与可视化》&#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 一、引言 1、Logstash简介 2、在K8s中部署Logstash多节点实例…

简单聊聊大数据分析的方法有什么

大数据分析是指对规模巨大的数据集合进行的分析过程。 这些数据集合通常具有以下几个特点&#xff0c;可以概括为5个V&#xff1a; 1.数据量大&#xff08;Volume&#xff09;&#xff1a;大数据分析处理的数据量巨大&#xff0c;远远超出了传统数据处理软件的能力范围。 2.…

MySQL Shell 使用指南

前言&#xff1a; MySQL Shell 是官方提供的 MySQL 周边适配组件&#xff0c;是新一代的高级客户端&#xff0c;在 MySQL 8.0 及其以后的版本得以慢慢推广应用。之前笔者因为 MySQL 8.0 用得比较少&#xff0c;一直没有详细使用过这个工具&#xff0c;近期在捣鼓 MySQL 8.0&am…

从入门到精通:Java Lambda运算符详解!

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。运营社区&#xff1a;C站/掘金/腾讯云&#xff1b;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一…

力扣 48.旋转图像

题目描述&#xff1a; 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],…

Alibbaba RocketMQ笔记

作用场景 异步解耦: 将比较耗时且不需要即时(同步)返回结果 的操作放入消息队列; 流量削峰: 历史简介 基本使用 深入了解\原理

泛型基础及深入

泛型深入 泛型定义&#xff1a; JDK5引入的特性&#xff0c;可以在编译阶段约束操作的数据类型&#xff0c;并进行检查 泛型格式&#xff1a; <数据类型> 注意&#xff1a;泛型只能支持引用数据类型 优势&#xff1a; 统一数据类型&#xff1b; 把运行时期的问题提前到…

JavaWeb_SpringBootWeb案例

环境搭建&#xff1a; 开发规范 接口风格-Restful&#xff1a; 统一响应结果-Result&#xff1a; 开发流程&#xff1a; 第一步应该根据需求定义表结构和定义接口文档 注意&#xff1a; 本文代码从上往下一直添加功能&#xff0c;后面的模块下的代码包括前面的模块&#xff0c…

WPF入门--多种方式设置样式(Style)

前言 在上篇文章中&#xff0c;介绍了WPF九种布局方式。本篇文章通过多种方式设置样式&#xff08;Style&#xff09;以控制UI元素的外观和行为。下面来具体介绍一下。 传送门 WPF入门--常用布局方式 目录 前言 一、直接在XAML中设置属性&#xff08;内联样式&#xff09…

【机器学习】使用Stable Diffusion实现潜在空间搜索

1、引言 1.1 潜在空间的概念 潜在空间&#xff08;Latent Space&#xff09;是在机器学习和深度学习中一个重要的概念&#xff0c;它指的是用于表示数据的一种低维空间。这个空间编码了数据中包含的所有有用信息的压缩表示&#xff0c;通常比原始数据空间的维数更低&#xff…

Python | Leetcode Python题解之第136题只出现一次的数字

题目&#xff1a; 题解&#xff1a; class Solution:def singleNumber(self, nums: List[int]) -> int:return reduce(lambda x, y: x ^ y, nums)

攻防世界---misc---津门杯2021-m1

1、题目描述&#xff0c;下载附件是一张bmp格式的图片 2、直觉告诉我这和图片的颜色通道有关 3、于是我就尝试用stegslove打开图片 4、将颜色通道都改为0&#xff0c;点击preview 5、然后发现一串base64编码 6、解码得flag flag{l5DGqF1pPzOb2LU919LMaBYS5B1G01FD}

CSS真题合集(一)

CSS真题合集&#xff08;一&#xff09; 1. 盒子模型1.1 盒子模型的基本组成1.2 盒子模型的实际大小1.3 盒子模型的两种类型1.4 设置盒子模型1.5 弹性盒子模型 2. BFC2.1 主要用途2.2 触发BFC的方法2.2 解决外边距的塌陷问题&#xff08;垂直塌陷&#xff09; 3. 响应式布局3.1…