闫式dp 分析法

#include <iostream>
#include <cstring>

using namespace std;
const int N = 3010;
int a[N] , b[N];
int f[N][N];
int 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];


    for (int i = 1 ;  i <= n ; i ++ ) {
        int maxv = 1;
        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] , maxv);
            else if (b[j] < a[i]) maxv = max(f[i][j] + 1 , maxv);
        }
    }

    /* 省去一维做法
        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 maxv = 1;
                    for (int k = 1 ; k < j ; k ++ ) 
                        if (b[k] < a[i]) maxv = Math.max(f[i - 1][k] + 1 , maxv);

                    f[i][j] = Math.max(f[i][j] , maxv);    
                }
            }
        }
    */
    int res = 0;
    for (int i = 1 ; i <= n ; i ++ ) res = max(res,f[n][i]);
    cout << res;
    return 0;
}