$O(N^2)$优化版本

#include <bits/stdc++.h>
using namespace std;

const int N=3005;
int n;
int a[N], b[N];
int f[N][N];

int main(){
    memset(f, 0x00, sizeof f);
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i];
    for(int i=1; i<=n; ++i) cin>>b[i];

    // f[i][j]表示所有a[1~i], b[1~j]中以b[j]为结尾的公共上升子序列集合
    // f[i][j]表示该集合子序列中长度最大的值
    for(int i=1; i<=n; ++i){
        int ans=1; // 记录以a[i]和b[j]为结尾的LICS长度
        for(int j=1; j<=n; ++j){
            f[i][j]=f[i-1][j];
            if(a[i]==b[j]) f[i][j]=max(f[i][j], ans);
            if(a[i]>b[j]) ans=max(ans, f[i-1][j]+1);
        }
    }

    int res=0;
    for(int i=1; i<=n; ++i) res=max(res, f[n][i]); 
    cout<<res<<endl;

    return 0;
}

$O(N^3)$暴力(当出现大量a[i]==b[j]时会TLE)

#include <bits/stdc++.h>
using namespace std;

const int N=3005;
int n;
int a[N], b[N];
int f[N][N];

int main(){
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i];
    for(int i=1; i<=n; ++i) cin>>b[i];

    // f[i][j]表示所有a[1~i], b[1~j]中以b[j]为结尾的公共上升子序列集合
    // f[i][j]表示该集合子序列中长度最大的值
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            f[i][j]=f[i-1][j];
            if(a[i]==b[j]){
                int ans=1; // 记录以a[i]=b[j]为结尾的LICS长度
                for(int k=1; k<j; ++k) // 枚举序列中倒数第二个数
                    if(a[i]>b[k]) ans=max(ans, f[i-1][k]+1);
                f[i][j]=max(f[i][j], ans);
            }
        }
    }
    int res=0;
    for(int i=0; i<=n; ++i) res=max(res, f[n][i]); 
    cout<<res<<endl;

    return 0;
}

python

from typing import List
class Solution:
    def main(self, n:int, a:List[int], b:List[int]):
        f=[[0 for _ in range(n+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            ans=1
            for j in range(1, n+1):
                f[i][j]=f[i-1][j]
                if a[i-1]==b[j-1]: f[i][j]=max(f[i][j], ans)
                if a[i-1]>b[j-1]: ans=max(ans, f[i-1][j]+1)
        res=0
        for i in range(1, n+1):
            res=max(res, f[n][i])
        print(res)

if __name__ == '__main__':
    sol=Solution()
    n=int(input())
    a=list(map(int, input().split()))
    b=list(map(int, input().split()))
    sol.main(n, a, b)