最长公共上升子序列-简明讲解

· · 个人记录

最长公共上升子序列，唯一不用说的一点就是两层循环，分别扫过a_i,b_j两个数列看看哪个对应相等（即a_i=b_j)

（注：本文内dp_i为内循环数组当前最长子序列长度，lnk为（前）链式记录数组）

将 内循环（j循环）扫过的数列 称为 对照数列，以这个数列作为dp的根源——其实和LIS的dp[i]=max(dp[i],dp[j]+1)类似，我们需要在b数组内找到一个 最优的 继承位置（这里设为tail，代码中为t，初值为0），类推下来，基础方程应该是dp[j]=dp[t]+1。

这个时候有人会问了，为什么不（用）取max了？有个贪心的解释就是，后面有结果能更新的话比前面的结果对当前对象贡献更优，所以在内循环（j循环）从前往后扫的时候已经保证，能用来更新的j(a[i]==b[j])，一定能成为最优解（先更新t，即更新最优的继承位置，确认t是当前对于更新后面（j+1往后）的最优位置后，j循环扫到后面再更新即可）

听起来可能有点玄乎，咱贴份代码（带输出最长公共子序列，链式倒序输出（栈，递归 等）即可）

#include<iostream>
#include<stack>
using namespace std;
int a[550],b[550],dp[550],lnk[550];
int main(){
    int n,m;
    cin>>n;//任意长度
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;//任意长度
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        int t=0;
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]){
                dp[j]=dp[t]+1;
                lnk[j]=t;
            }
            if(a[i]>b[j]&&dp[t]<dp[j]) t=j;//解决到j以后为后面着想
        }
    }
    int p;//记录最长公共子序列的结尾位置
    for(int i=1;i<=m;i++){
        if(dp[i]>dp[p]) p=i;
    }
    cout<<dp[p]<<endl;
    stack<int>s;
    while(p!=0){
        s.push(p);
        p=lnk[p];
    }
    while(!s.empty()){//倒序从前往后输出，故用栈（或递归）输出
        int now=s.top();
        cout<<b[now]<<" ";
        s.pop();
    }
    return 0;
}

（时间复杂度：nm，空间复杂度：n+m）