线性 DP 五大经典模型：LIS、LCS、合唱队形、编辑距离详解与模板

经典线性 dp 问题有两个：最长上升子序列（简称：LIS）以及最长公共子序列（简称：LCS），这两道题目的很多方面都是可以作为经验，运用到别的题目中。比如：解题思路，定义状态表示的方式，推到状态转移方程的技巧等等。因此，这两道经典问题是需要我们重点掌握的。

最长上升子序列

题目解析 本题介绍最长上升子序列的一般解法，当数据量不大时用这种解法。在此之前，先区分一下子数组和子序列，子数组需要是连续的，而子序列可以是间断的。

1、状态表示 dp[i] 表示以 i 结尾的所有子序列中，最长的上升子序列。 2、状态转移方程 还是以最后一步推导状态转移方程，分两种情况： 一、当序列长度为 1 时，因为 dp[i] 自己本身就是一个子序列，所以 dp[i] 的最小取值可能是 1（比如总序列是一个递减序列的话，那么每个 dp[i] 的取值都会是 1） 二、当序列长度大于 1 时，如果第 i 个格子前面的所有格子中有比第 i 个格子小的格子，记为 j，那么第 i 个格子就可以挂在 j 格子后面组成一个序列，序列长度就是 dp[j] 加 1，因为我们要求最长上升子序列，所以需要遍历 dp 数组中从 1 到 i-1 的所有值，找出所有 a[j] 小于 a[i] 的格子，从中选出 dp[j] + 1 的最大值，该值为 dp[i] 的取值。

3、初始化 因为我们没遍历到一个格子都会先把 dp[i] 置为 1，所以 dp 数组不用初始化，用默认值 0 即可。 4、填表顺序 从左往右 5、输出结果 结果为 dp 数组从 1 到 n 的所有取值的最大值。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int n;
int a[N], dp[N];
int main(){
    //处理输入
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    //初始化
    //按序填表
    int ret = 0;
    for(int i = 1; i <= n; i++){
        dp[i] = 1;
        for(int j = 1; j < i; j++){
            //选出 dp 数组中 1 到 i-1 所有格子的最大值，把最大值加一赋给 dp[i]
            if(a[j] < a[i]){
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        ret = (ret, dp[i]);
    }
    cout << ret << endl;
     ;
}