DP：子序列模型
https://img-blog.csdnimg.cn/direct/a9200829b07c49a08ab9ec7909364371.gif子数组vs子数列
1、子数组（n^2） 子序列(2^n)
2、子数组是子序列的一个子集
3、子数组必须一连，子序列可以不一连
一、最长递增子序列
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/d32266a21d8240f3a99d33a0a8fac6b6.png
算法原理：
1、状态表现（经验+题目要求）
dp表现以i位置为末端全部子系列中，最长递增子序列的长度。
2、状态转移方程
（1）长度为1——>dp=1
(2) 长度大于1——>满足条件（nums<nums）——>max(dp+1,dp) （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<nums) dp=max(dp+1,dp); //前提条件要满足
return *max_element(dp.begin(),dp.end());//dp数组中的最大值
}
}; 二、摆动序列
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/9905e24a4d8f460a972792b8bc1b9ba8.png
算法原理：
1、状态表现（经验+题目要求）
dp表现以i位置为末端全部子序列中，最长递增子序列的长度。 （错误）
由于会存在两种状态，所以我们必要两个dp数组：
f表现以i位置为末端的全部子序列中，最后一个位置出现“上升”趋势的最长摆动序列的长度
g表现以i位置为末端的全部子序列中，最后一个位置出现“下降”趋势的最长摆动序列的长度
2、状态转移方程
f（上升）:
（1）长度为1——>1
(2) 长度大于1——>满足条件（nums<nums）——>max(g+1,f) （0<=j<=i-1）
g（下降）:
（1）长度为1——>1
(2) 长度大于1——>满足条件（nums>nums）——>max(f+1,g) （0<=j<=i-1）
3、初始化
如果无法更新，最差情况本身也是一个子序列，所以g表和f表全都初始化为1
4、填表顺序
必要借助前面的状态，所以要从左往右，两个表一起填
5、返回值
两个表中的最大值
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
//f表示以i位置结尾的最长子序列中，最后呈现上升趋势 （前提nums<nums）
//g表示以i位置结尾的最长子序列中，最后成下降趋势 (前提nums>nums)
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<nums)g=max(f+1,g);
else if(nums>nums) f=max(g+1,f);
return max(*max_element(f.begin(),f.end()),*max_element(g.begin(),g.end()));
}
}; 三、最长递增子序列的个数
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/096bf78c1295468ea24c6bfe28907f3a.png
在教学前先来个小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位置为末端全部子序列中，最长递增子序列的个数。 （错误）
由于我们在填表的时候并不能确认最长递增子序列的长度是多少，所以无法直接统计。我们就得用demo中的方案2的思想，来解决这个题目。
len表现以i位置为末端的全部子序列中，最长递增子序列的“长度”
count表现以i位置为末端的全部子序列中，最长递增子序列的“个数”
2、状态转移方程
nums<nums时
（1）len+1==len——>count+=count
（2）len+1<len 无视
（3）len+1>len——>len=len+1 count=count（更新最大值并重新计数）
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>nums) //构成子序列的前提条件
if(len+1==len)count+=count;
else if(len+1>len)len=len+1,count=count;
//更新一下最长长度和最大数
if(retlen==len) recount+=count;
else if(retlen<len)
{
retlen=len;
recount=count;
}
}
return recount;
}
}; 四、最长数链对
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/31f82c34f0ec4499bc7a8ff46f22248f.png
算法原理：
预处理：由于题目要求是任意顺序组成数链对，所以我们在处理的时候不仅要思量前面，还要思量背面，这样倒霉于我们的动态规划表现，所以我们要先按照第一个元素举行排序(好比 ，a<c<d 所以d>a,所以背面的不必要思量到)，我们要举行sort，在C++中，vector、pair的默认比力逻辑都是按照字典序的，恰好符合我们的要求，所以我们可以直接调用sort。
https://img-blog.csdnimg.cn/direct/ddf2f2fe82b94293891f29b324c84dfe.png
1、状态表现（经验+题目要求）
dp表现以i位置为末端全部数对链序列中，最长数对链的长度。
2、状态转移方程
dp:
(1)长度为1——1
(2)长度大于1——p>p ——max(dp,dp+1)
3、初始化
初始化为1
4、填表顺序
必要借助前面的状态，所以要从左往右
5、返回值
要返回dp表中的最大值，但由于我们排序过，所以最大值必然出如今dp。
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<pairs) dp=max(dp+1,dp);//(1,5)(2,3)(4,10)(5,9)
return dp;//最大值必然在最后面
}
}; 五、最长定差子序列（经典）
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/dd4f6f4d3d324619b7611761125b4b32.png
算法原理：
1、状态表现（经验+题目要求）
dp表现以i位置为末端全部子序列中，最长的等差子序列长度
2、状态转移方程
dp:
(1)b不存在——>1
(2)b存在——>取最后一个即可dp+1
我们会发现前一个数基本上是可以确定是多少的，而且有多个的话也可以用背面的覆盖前面的，因此我们可以用哈希表做优化
优化思绪：
（1)将元素+dp的值存在哈希表中
（2)直接在哈希表中做动态规划
3、初始化
hash]=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=hash+1; //因为v-difference不在的时候，会被自己创建出来并初始化为0
ret=max(ret,hash);
}
return ret;
}
}; 为什么哈希表不必要先将数组中的元素全部初始化为1？？？由于hash=hash+1,当v-differences不存在的时候，重载方括号会去调用insert并答应我们修改second，在创建的时候初始化了。
六、最长的斐波那契子序列长度
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/0934d4222b1345b9ac9599e42f4a7d61.png
算法原理：
1、状态表现（经验+题目要求）
dp表现以i位置为末端全部子序列中，最长的斐波那契子序列长度（错误）。
由于我们至少得确定两个位置，才气知道序列是否满足斐波那契子序列的要求。
dp表现以i位置及j位置为末端全部子序列中，最长的斐波那契子序列长度。
2、状态转移方程
dp: （假设abc对应的坐标分别是kij）
(1)如果a存在且a<b——>dp+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]=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-arr;
if(hash.count(a)&&a<arr) dp=dp]+1;
ret=max(dp,ret);
}
return ret==2?0:ret;
}
}; 七、最长等差数列
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/6a9c44bfd5f44cf1bc76be96896cd0a1.png
算法原理：
1、状态表现（经验+题目要求）
dp表现以i位置为末端全部子序列中，最长的等差子序列的长度（错误）。
由于我们至少得确定两个位置，才气知道序列是否满足等差子序列的要求。
dp表现以i位置及j位置为末端全部子序列中，最长的等差子序列长度。
2、状态转移方程
dp: （假设abc对应的坐标分别是kij）
(1)如果a存在且a<b——>dp+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]=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-nums;
if(hash.count(a)) dp=dp]+1;
ret=max(dp,ret);
}
hash]=i;//记住最后一个即可
}
return ret;
}
}; 八、等差数列划分II-子序列
. - 力扣（LeetCode）
https://img-blog.csdnimg.cn/direct/b083c35b5c7846a88d76949269e8943e.png
算法原理：
1、状态表现（经验+题目要求）
dp表现以i位置为末端全部子序列中，最长的等差子序列的长度（错误）。
由于我们至少得确定两个位置，才气知道序列是否满足等差子序列的要求。
dp表现以i位置及j位置为末端全部子序列中，最长的等差子序列长度。
2、状态转移方程
dp: （假设abc对应的坐标分别是kij）
(1)如果a存在且a<b——>dp+=dp+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、细节处理
https://img-blog.csdnimg.cn/direct/a50e9bbbb06b40cc975e143ec5955ac4.png
可能会溢出，所以我们要下标要存储long
https://img-blog.csdnimg.cn/direct/83e0dd166d0f433cbfb37d88c608e9f4.jpeg
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]