python/TangDou/AcWing/LIS/272.md

##[$AcWing$ $272$. 最长公共上升子序列](https://www.acwing.com/problem/content/274/)

### 一、题目描述

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究 **最长公共上升子序列** 了。

小沐沐说，对于两个数列 $A$ 和 $B$，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列 $A$和 $B$ 的长度均不超过 $3000$。

**输入格式**

第一行包含一个整数 $N$，表示数列 $A，B$ 的长度。

第二行包含 $N$个整数，表示数列 $A$。

第三行包含 $N$个整数，表示数列 $B$。

**输出格式**

输出一个整数，表示最长公共上升子序列的长度。

**数据范围**

$1≤N≤3000$,序列中的数字均不超过 $2^{31}−1$。

**输入样例**：
```cpp {.line-numbers}
4
2 2 1 3
2 1 2 3
```

**输出样例**：
```cpp {.line-numbers}
2
```

### 二、前导知识

**[$AcWing$ $895$. 最长上升子序列](https://www.cnblogs.com/littlehb/p/15425546.html)**

**状态表示** 
$f[i]$表示从第一个数字开始算，以$a[i]$ **<font color='red'>结尾</font>** 的最长的上升序列长度。(以$a[i]$结尾的所有上升序列中属性为**最长**的那一个)

**状态计算** 

$$ \left\{\begin{array}{l}
f[i] =1  &  默认值，前面没有比i小的，以a[i]结尾的最长个数是1 \\
f[i] = max(f[i], f[j] + 1) & 0 \le j<i \ \& \  a[j]<a[i] 
\end{array}\right.
$$


**[$AcWing$ $897$. 最长公共子序列](https://www.cnblogs.com/littlehb/p/15429296.html)**

定义$f[i][j]$是$a[]$以$i$结尾，$b[]$以$j$结尾的 **最长公共子序列长度**，但没有说$a[i]$或者$b[j]$一定要出现在最长公共子序列当中！这个最长公共子序列，可能是$a[]$和$b[]$的一些前序组成的，$a[i],b[j]$也可能没有对结果产生贡献。

$
\large \left\{\begin{array}{l}
f[i][j]=f[i-1][j-1]+1 & a[i]=b[j] \\ 
f[i][j]=max(f[i-1][j],f[i][j-1]) & a[i] \neq b[j] 
\end{array}\right.
$

### 三、本题解法
闫氏$DP$分析法：(结合了$LCS$与$LIS$的状态表示的方法，可以很直接的发现二者的影子)

#### 状态表示 

- $f[i][j]$—集合：考虑 $a$ 中前 $i$ 个数字，$b$ 中前 $j$ 个数字 ，且当前以 $b[j]$ 结尾的子序列的方案

- $f[i][j]$—属性：$max($所有符合条件方案的子序列长度$)$

#### 状态转移
- $\large a_i \neq b_j$
 考虑 $a$ 数组中前$i-1$个数字， $b$数组中前$j$个数字 ，且当前以 $b[j]$ 结尾的子序列的方案转移过来：
$$\large f[i][j]=max(f[i][j],f[i−1][j])$$

- $\large a_i = b_j$
 考虑 $a$ 数组中前$i-1$个数字， $b$数组中前 $k$ 个数字 ，且当前以 $b[k]$ 结尾的子序列的方案转移过来：
$$\large f[i][j]=max(f[i][j],f[i−1][k]+1),k∈[0,j−1],a_i=b_j,b_j>b_k$$

按上述思路实现，需要三重循环：

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

const int N = 3010;
int a[N], b[N];
int f[N][N];
int res;
// 通过了 10/13个数据
// O(n^3)
int main() {
    int n;
    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++)
        for (int j = 1; j <= n; j++) {
            // ① 二维DP打表的一般套路，都是可以直接从上一行继承的
            // ② 从题意出发，就是a中前i个数字，b中前j个数字，且以b[j]结尾的子序列中长度最大的
            // 那么，a中多整出一个数字来，最起码也是f[i-1][j]的值，不能更小
            f[i][j] = f[i - 1][j];
            // ③ 如果恰好 a[i]==b[j],那么就可以发生转移
            if (a[i] == b[j]) {
                int mx = 1; // 最起码a[i]==b[j]，有一个数字是一样嘀~
                // f[i-1]是肯定的了，问题是b的前驱在哪里？需要枚举1~j-1
                for (int k = 1; k < j; k++)
                    if (b[j] > b[k]) // 需要上升
                        // 找出公共且最长的
                        mx = max(mx, f[i - 1][k] + 1);
                // 更新答案
                f[i][j] = max(f[i][j], mx);
            }
        }
    int res = 0;
    // a数组肯定是火力全开到n就行，b数组中的位置就需要枚举了
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}
```

###　四、优化

**$Q$:朴素办法超时($10/13$)，如何优化？**

观察到，对于第二种状态转移：$f[i][j]=max(f[i][j],f[i−1][k]+1) \ k∈[0,j−1],a_i=b_j,b_j>b_k$

每次用到的 **状态** 都是第 $i - 1$ 个阶段的

因此我们可以用一个变量，存储上一个阶段的能够接在 $a[i]$ 前面的最大的状态值

最终答案枚举子序列结尾取最大值即可。

#### 实现代码$O(N^2)$
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 3010;
int a[N], b[N];
int f[N][N];
int res;

// O(n^2)
int main() {
    int n;
    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 mx = 1;
        for (int j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = mx;
            if (a[i] > b[j]) mx = max(mx, f[i - 1][j] + 1);
        }
    }

    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    printf("%d\n", res);

    return 0;
}

```

### 五、空间优化
本题还可以继续优化成一维数组，但在现实中意义不大。
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

const int N = 3010;

int a[N], b[N], 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];

    for (int i = 1; i <= n; i++) {
        int maxv = 1;
        for (int j = 1; j <= n; j++) {
            if (a[i] == b[j]) f[j] = max(maxv, f[j]);
            if (a[i] > b[j]) maxv = max(f[j] + 1, maxv);
        }
    }

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

    cout << res << endl;
    return 0;
}

```