一、前导知识
二、本题思路
1、理解样例
2 2 1 3
2 1 2 3
两个序列，要求严格上升子序列，那么上面的那个序列中的严格上升子序列为
2 3
1 3
下面的序列中严格上升的子序列为
2 3
1 2
1 3
两个相同的，最长的为
1 3
2 3
长度是\(2\)，答案输出\(2\)。
2、解题关键
(1)状态表示
\(f(i,j)\)是以\(b[j]\)为结尾的\(lcis\)（最长公共上升子序列）。
(2)状态计算
① \(f(i,j) = f(i-1,j)\) \((a[i] != b[j])\)
② \(f(i,j) = max(f(i-1,k)+1)\) \((1 <= k <= j-1 \&\& b[j] > b[k])\)
现在我们来说为什么会是这样的状态转移方程呢？
①:在\(a[i]!=b[j]\)的情况下必然有\(f(i,j)=f(i-1)(j)\)。
②:前提是\(a[i] == b[j]\),需要去找一个最长的且能让\(b[j]\)接在其末尾的\(lcis\)。
之前最长的\(lcis\)在哪呢？
-
第一维必然是\(i-1\)。因为\(i\)已经拿去和\(b[j]\)配对去了，不能用了。并且也不能是\(i-2\)，因为\(i-1\)必然比\(i-2\)更优。
-
第二维呢？那就需要枚举\(b[1]…b[j-1]\)了，因为你不知道这里面哪个最长且哪个小于\(b[j]\)。
三、实现代码O(N^3)
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int n; //此题目的数组长度，两个数组是一样的长度
int a[N]; //数组a
int b[N]; //数组b
/*二维DP数组，第一维表示数组a中第i个位置，第二维表示数组b中第j个位置，
并且以b[j]为结尾的上升子序列的集合，value=Max(集合内容)。
之所以这样定义数组的含义，可以参考LIS和LCS的思想，糅合到一起形成了这样一个二维状态表示。
*/
int f[N][N];
//朴素O(N^3)版本，N<=3000,所以3次方会超时，需要优化。
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++) //遍历a数组
for (int j = 1; j <= n; j++) { //遍历b数组
//如果a[i]!=b[j]，那么a[i]无法为结果f[i][j]做出贡献 ，所以：f[i][j] = f[i - 1][j]
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) {
//a[i]!=b[j]时很简单，麻烦的是相等
//如果a[i]==b[j],那么f[i][j]的值就应该是前面a[1,i-1],b[1,j-1]中所有可能的最长上升公共子序列+1
//如果没有其它的，那么还有a[i]==b[j]，最长的上升公共子序列值最小是1
int mx = 1;
/*具体是从哪个状态可以迁移到f[i][j]这个状态呢?不知道，需要逐个讨论一下。
(1)对于 1~j-1的每个b中元素，哪个可能是b[j]接上去形成最长上升子序列呢？都是有可能的，全部扫描一遍。
(2)对于k∈[1~j-1]，所有满足小于b[j]的f[i][k]都是有机会的，需要取它们的最大值。
*/
for (int k = 1; k < j; k++)
if (b[k] < b[j])//只有可能接的上去的才有资格讨论
mx = max(mx, f[i - 1][k] + 1);//之所以+1,是因为a[i]=b[j]
//更新f[i][j]的最大值
f[i][j] = mx;
}
}
//找出最大值
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}
可以发现a[i] == b[j]情况下if (b[j] > b[k])可等同于if (a[i] > b[k])，
for (int k = 1; k < j; ++ k)
if (a[i] > b[k]) // b[j] > b[k]
f[i][j] = max(f[i][j], f[i - 1][k] + 1);
所代表意义为求满足a[i] > b[k]情况下所有的f[i - 1][k] + 1的最大值,无需遍历k，可在前两个循环中求出
四、实现代码O(N^2)
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
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];
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);
}
}
//输出
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}
五、终极优化解法（一维+O(N^2)）
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N];
int res;
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 mx = 1;
for (int j = 1; j <= n; j++) {
if (b[j] < a[i]) mx = max(mx, f[j] + 1);
if (b[j] == a[i]) f[j] = mx;
}
}
for (int i = 1; i <= n; i++) res = max(res, f[i]);
printf("%d\n", res);
return 0;
}