前言：此文章是观看下方这个讲解视频后总结的 只是小生非常浅薄的一些理解 若是有读者发现不足之处 请积极指正呀！

https://www.bilibili.com/video/BV1AB4y1w7eT/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=7241ee420f0d3967b1f6671d1406ae0f

正文：
题目描述：

求数组a中的最长递增子序列的长度.

  • 第一行输入一个整数n.（0<=n<=1e7)
  • 第二行输入n个整数t.（0<=t<=1e9）
输入样例
5
1 5 2 4 3
输出样例
3
代码部分：
  • 方法一：爆搜 alt
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int a[N],n;
int Maxlength=-0x3f3f3f3f;
// 计算从u这个点开始的最长子序列 
int dfs(int u)
{
	if(u==n) return 0;
	//回溯到第一层才知道最终答案
	int cnt=0;
	for(int i=u+1;i<n;i++)
	{
		if(a[i]>a[u]) cnt=max(cnt,dfs(i));
	}
	return cnt+1;
    // 时间：1ms 
    
	//回溯到第二层知道答案
	int cnt=1;
	for(int i=u+1;i<n;i++)
	{
		if(a[i]>a[u]) cnt=max(cnt,dfs(i)+1);
   // 在当前的最大值cnt和从第i个位置往后的最长子序列长度(即dfs(i)) 且 加上本身u这个位置(即+1)之后的值即(dfs(i)+1)；两者之间求最大值(即cnt与dfs(i)+1求最大)
	}
	return cnt;
	// 时间：2ms
}
int main ()
{
	cin>>n;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<5;i++)
	{
		Maxlength=max(Maxlength,dfs(i)); 
	}
	cout<<Maxlength<<endl;
	return 0; 
}
  • 方法二：记忆化搜索
    即：开一个数组b记录从每个点开始的最长的递增子序列的长度
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int a[N],n,b[N];
int Maxlength=-0x3f3f3f3f;
int dfs(int u)
{
	if(u==n) return 0;
	if(b[u]!=-1) return b[u];
	int cnt=0;
	for(int i=u+1;i<n;i++)
	{
		if(a[i]>a[u])
		{
			cnt=max(cnt,dfs(i));
		}
	}
	b[u]=cnt+1;
	return b[u];
	// 时间：1ms 
}
int main ()
{
	memset(b,-1,sizeof b);
	cin>>n;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
	{
		Maxlength=max(Maxlength,dfs(i)); 
	}
	cout<<Maxlength<<endl;
	return 0; 
}
  • 方法三：动态规划
    即 找到递归最底层 采用迭代法由最底层向上递推
// 思路
/*
 a[5]={2,5,3,4,1}
 
 l[0]=max{l[1],l[2],l[3],l[4]}+1;
 l[1]=max{l[2],l[3],l[4]}+1;
 l[2]=max{l[3],l[4]}+1;
 l[3]=max{l[4]}+1;
 l[4]=1;
*/
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int a[N],n;
int l[N];// 记录从每个位置往后的最长子序列长度 

int main ()
{
	int Maxlength=-0x3f3f3f3f;
	cin>>n;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++) l[i]=1;// 初始时每个位置只有自身的长度 1；
	
	// 从后往前推,i从4开始 
	for(int i=n-1;i>=0;i--)
	{
		// 从i后面的一个位置开始 寻找否有大于a[i]的点 
		for(int j=i+1;j<n;j++)
		{
			if(a[j]>a[i])
			{
				l[i]=max(l[i],l[j]+1);
				//d[i] 当前从i位置往后的最长子序列
				//d[j]+1 找到的大于a[i]的j位置 d[j]+1从j位置到往后的最长子序列 加上i本身这个位置
				Maxlength=max(Maxlength,l[i]); 	
			}
		}
	}
	cout<<Maxlength<<endl;
	return 0; 
}
结尾语：

类似的思路和题目有：
https://blog.nowcoder.net/n/a942b3f943084c4c8c03e12a894f86bc 求最大的滑行距离（也就是二维空间内某个起点到终点的最大路径距离）
http://lx.lanqiao.cn/problem.page?gpid=T3000 求可拿的最大金币量（同上题一样的道理）
本题是一维空间内求最长的递增序列（因为没要求连续，所以每个结点的分结点会更多一点）