算法1

(暴力枚举dp) $O(n^3)$

思路：首先考虑状态f[i][j] : 由a[0~i]和b[0~j]构成的且以b[j]为结尾的公共上升子序列
集合划分：
a[i]不在公共上升子序列中:f[i-1][j];
a[i]在公共上升子序列中：
    根据定义易得：a[i] == b[j]
    则f[i][j] = max(f[i][k]+1) (b[j] > b[k] , k = 1~j-1)
    由于b[j] == a[i],则a[0~i] ∩ b[0,j-1] 一定会有是因为：
    i从小到大更新，由a[i]==b[j]确保交集的存在

C++ 代码

#include <iostream>

using namespace std;

const int N = 3010;

int f[N][N] ;  
int a[N] , b[N];
int n ;

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

    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++ ){
            //如果不相等,包含a[i]
            f[i][j] = f[i-1][j];    

            if(a[i] == b[j]){    //包含a[i],f[i-1][0~j-1]
                for(int k = 0 ; k < j ; k++)    
                    if(b[j] > b[k])
                        f[i][j] = max(f[i][j],f[i][k]+1);

                //注意这里k需要是0而不是1，注意空集
                //否则当(1,1)时,如果相等则无法完成加一
            }

        }
    }

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

    return 0;
}

算法2

(dp迭代版) $O(n^2)$

由上式可以发现，每次去枚举f[i][1~j-1]其实是没有必要的，因为一旦之前的状态确定后就不会发生改变。
为此我们为什么不直接在循环的过程中就把这个值记录下来呢？
并且由于枚举跟新操作只发生在a[i] == b[j]时，
因此上式的b[j]>b[k]可等效代替为a[i]>b[k],也就暗含了k这一维度是可以省略的。

给出mx的定义：
当a[i]==b[j]时，mx = max(f[i][0~j-1])+1 (由于此处已经隐含了在下一步相等时的值，因此别忘了初始值应该为1)
由此我们可以直接在a[i] == b[j]时得出：f[i][j] = max(f[i][j],mx);

那么在省去内部循环之后又该在什么时候跟新mx呢？
不难发现,当a[i]>b[j]时,详情请看代码的注释部分

C++ 代码

#include <iostream>

using namespace std;

const int N = 3010;

int f[N][N] ; 
int a[N] , b[N];
int n ;

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

    for(int i = 1 ; i <= n ; i++){
        int mx = 1 ;    //记录max(f[i][0~j-1])+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],mx);

            if(a[i] > b[j]) //上升，包含a[i]且以b[j]结尾
                mx = max(mx , f[i][j]+1);   //确保在下次遇到相等时能够直接用mx更新f[i][j];
            //相当于只是把当前的b[j]加入f[i][j']的公共上升序列中
            //其中j'是紧接着这个j的下一个满足a[i]==b[j']的"j";

            /*
            cout << f[i][j] << ":" << mx << '\t';
                1 5 3 6 3 2 7 3 6 2 
                9 6 2 3 1 5 3 3 6 1

                0:1 0:1 0:1 0:1 1:1 0:1 0:1 0:1 0:1 1:1 
                0:1 0:1 0:1 0:1 1:2 2:2 0:2 0:2 0:2 1:2 
                0:1 0:1 0:1 1:1 1:2 2:2 2:2 2:2 0:2 1:2 
                0:1 1:1 0:1 1:2 1:2 2:3 2:3 2:3 3:3 1:3 
                0:1 1:1 0:1 1:1 1:2 2:2 2:2 2:2 3:2 1:2 
                0:1 1:1 1:1 1:1 1:2 2:2 2:2 2:2 3:2 1:2 
                0:1 1:2 1:2 1:2 1:2 2:3 2:3 2:3 3:4 1:4 
                0:1 1:1 1:2 2:2 1:2 2:2 2:2 2:2 3:2 1:2 
                0:1 1:1 1:2 2:3 1:3 2:3 2:3 2:3 3:3 1:3 
                0:1 1:1 1:1 2:1 1:2 2:2 2:2 2:2 3:2 1:2

            */
        }
        cout << endl;
    }


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

    return 0;
}