1、算法描述

第一步：构建一个一维dp数组，dp[i] 的意义为从第一个点 到 第i个点（一定包括第i个点）的最长递增子序列。
第二步：对此dp数组赋初值为1，因为 最长递增子序列 的最小值为1 ，即本点到本点。
第三步：遍历从第一个点到第i-1个点，用j来表示。然后维护dp数组：
如果a[j] -> a[i] 是递增关系的话： 更新dp[i] = max( dp[j+1] , dp[i] )。

2、例题：

最长上升子序列 - Acwing

3、代码：

#include <cstdio>
#include <iostream>
using namespace std;

int n;
int a[1005];
int dp[1005];

int main(void) {
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> a[i];
        dp[i] = 1;
    }
    int max = 1;//最长递增子序列的最小值为 1 
    for(int i=1;i<n;i++) {
        for(int j=0;j<=i-1;j++) {
            if(a[i] > a[j]) { //如果a[j] -> a[i]满足递增 
                if(dp[j] + 1 > dp[i]) { //并且此种方式（dp[j]+1） 比 之前的（dp[i]） 方式更好 
                    dp[i] = dp[j] + 1; //则替换当前 
                }
            }
            if(dp[i] > max) {
                max = dp[i];
            }
        }
    }
    cout << max << endl;
    return 0;
}

4、参考视频

最长上升子序列 动态规划 - Bilibili