关于dp:经典dp最长上升子序列

1、题目形容

给定一个长度为 N 的数列，求数值严格枯燥递增的子序列的长度最长是多少。输出格局第一行蕴含整数 N。第二行蕴含 N 个整数，示意残缺序列。输入格局输入一个整数，示意最大长度。

数据范畴
1≤N≤10001
−1e9≤数列中的数≤1e9。

输出样例
73 1 2 1 8 5 6

输入样例
4

2、思路分析

这是一道经典 dp 问题，咱们要求的是最长回升子序列的长度，这个最长的子序列可能是以 a[i] 结尾的（咱们假如数字被存储在数组 a 中），咱们应用一个数组 dp[i] 来示意以 a[i] 为结尾的子序列的最大长度，咱们最终所求的就是 dp 数组中的最大值。

如果咱们需要求 dp[i]，就是以 a[i] 为结尾的最大值，那么咱们就须要晓得它的前一个地位是谁，假如它的前一个数字是 a[j]，那么 dp[i] = dp[j] + 1，也就是以它前一个数字结尾的最大子序列长度再 +1。j 到底是谁咱们不分明，j 的范畴是 [1, i-1]，咱们把最大的（dp[j] + 1）找到，就是最大的 dp[i]。

3、代码

#include<iostream>
using namespace std;

const int N = 1e3+10;

int a[N],dp[N];

int main()
{
    int n;
    cin>>n;
    int M = 0;
    for(int i=1;i<=n;++i)cin>>a[i];
    
    for(int i = 1;i<=n;++i)// 求 dp[i] 汇合
    {dp[i] = 1;//dp[i] 起码也有本身的长度
        for(int j=1;j<i;++j)// 看看以 a[i] 结尾的最长子序列的前一个数是哪一个
        {if(a[j]<a[i])
            {dp[i] = max(dp[i], dp[j]+1);
            }
        }
        // 找最长子序列
        M = dp[1];
        for(int i=2;i<=n;++i)
        {M = max(M, dp[i]);   
        }
    }
    cout<<M<<endl;
    return 0;
}