思路分析

这道题目是AcWing 895. 最长上升子序列和AcWing 897. 最长公共子序列的结合版，在状态表示和状态计算上都是融合了这两道题目的方法。

状态表示：

f[i][j]代表所有a[1 ~ i]和b[i ~ j]中以b[j]结尾的公共上升子序列的集合；

f[i][j]的值等于该集合的子序列中长度的最大值；

首先三重循环的dp计算，很容易可以写出来，根据a[i] 和 b[j] 的关系，下面的代码有注释

难点在如何优化成二维，我参考了蓝书的讲法，首先仔细观察那个写出来的三重循环的 循环k 那层，我们能优化的只有这一层，如何避免循环呢，k 的变化范围是从 0 <= k <= j-1, 这层循环的目的是找到小于 a[i] 的所有b[k] , 然后根据 dp[i-1][k] 取个max， 所以我们可以考虑下用一个变量可不可以维护住这个最大值呢，我们设 val 代表 dp[i-1][k] 的最大值，在j那层循环，只要 b[j] < a[i] 我们就把它更新，这样就可以维护住所有b序列里下标小于j， 值小于 a[i] 的最大值

参考文章

https://www.geek-share.com/detail/2678442635.html

蓝书 P267

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int a[N], b[N];
int dp[N][N];//从起点到i，从起点到j并且以b[j]结尾的最大LICS
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];
    int ans = 0;
    //下面是n^3的代码，帮助理解
    /*
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            //不包含 a[i]
            dp[i][j] = dp[i-1][j];
            //包含
            if(a[i] == b[j]){
                //此时至少有一个LICS
                dp[i][j] = max(1, dp[i][j]);
                for(int k = 1;k < j;++k)
                    if(b[j] > b[k])
                        dp[i][j] = max(dp[i][j], dp[i-1][k] + 1);
            }
            ans = max(ans, dp[i][j]);
        }
    }
    */
    //接下来我们优化成n^2
    for(int i = 1;i <= n;++i){
        int val = 0;//从 dp[i-1][1] 到 dp[i-1][j - 1] 的最大值
        for(int j = 1;j <= n;++j){
            if(a[i] == b[j])
                dp[i][j] = val + 1;
            else
                dp[i][j] = dp[i-1][j];
            if(a[i] > b[j])
                val = max(val, dp[i-1][j]);//更新
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}