目录
一、前言
二、最长公共上升子序列
1、问题描述
2、基本思路
（1）状态表示
（2）状态计算
三、题例
1、上链接
2、基本思路
3、代码
（1）python未优化版
（2）python优化版
一、前言
对于学计算机的同学来说，学习算法是一件非常重要的事情，废话不多讲，我们来讲讲“最长公共上升子序列问题”。
二、最长公共上升子序列
1、问题描述
给定两个长度为 n 的数组 a[n]，b[n]
求两个数组的 最长公共上升子序列 长度
2、基本思路
首先，这个问题是两个经典 dp 模型的结合：
LIS (最长上升子序列，Longest Increasing Subsequence)
LCS (最长公共子序列，Longest Common Subsequence)
LCIS (最长公共上升子序列，Longest Common Increasing Subsequence)
使用闫氏dp分析法进行简单的思路分析。
（1）状态表示
集合f[i][j] ：考虑 a 中前 i 个数字，b 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案；
f[i][j]的性质：方案中子序列长度最大值——max
（2）状态计算
下面大部分引用y总原话：
首先依据公共子序列中是否包含 a[i]，将 f[i][j] 所代表的集合划分成两个不重不漏的子集：
（1）不包含a[i]的子集（即我不选 a[i]，因为 a[i]!=b[j]），显然最大值是 f[i - 1][j]；
（2）包含a[i]的子集（即我选 a[i]，因为 a[i]==b[j] 了），则需要将这个子集继续划分，依据是子序列的倒数第二个元素在 b[] 中是哪个数：
- 子序列只包含 b[j] 一个数，长度是1；
- 子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1；
- 子序列的倒数第二个数是b[2]的集合，最大长度是f[i - 1][2] + 1；
- .......
- 子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；
然后就是比较取最大值了。
即状态转移方程为:
f[i][j] = f[i−1][j] (a[i]≠b[j])
f[i][j] = max(f[i−1][j], f[i−1][t]+1) (a[i]==b[j])
三、题例
1、上链接
272. 最长公共上升子序列 - AcWing题库
2、基本思路
如上。
3、代码
（1）python未优化版
N=int(input())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
dp=[[0 for i in range(N+2)] for j in range(N+2)]
for i in range(1,N+1):
for j in range(1,N+1):
dp[i][j]=dp[i-1][j]
if a[i]==b[j]: # 公共
for k in range(1,j):
if b[j]>b[k]: #上升
dp[i][j]=max(dp[i][j],dp[i-1][k]+1)
print(max(dp[N]))
'''
时间复杂度：O(n^3)
毫无疑问会超时
这个代码主要是用来理解这个DP模型，因为接下来的优化，和DP无关，是代码的等价变形
'''
'''
/*另一个三重循环*/
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 (a[i] > b[k])
maxv = max(maxv, f[i - 1][k] + 1);
f[i][j] = max(f[i][j], maxv);
}
}
}
'''（2）python优化版
N=int(input())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
dp=[[0 for i in range(N+2)] for j in range(N+2)]
for i in range(1,N+1):
maxv=1
for j in range(1,N+1):
dp[i][j]=dp[i-1][j]
if a[i]==b[j]:
dp[i][j]=max(dp[i][j],maxv)
if b[j]<a[i]:
maxv=max(maxv,dp[i-1][j]+1) #为什么这样更新最大值其实我没有很懂
#后面懂了，因为k是对j的枚举，对代码的等价变形，先看看上面朴素法三重循环有maxv版
print(max(dp[N]))
'''
然后我们发现每次循环求得的maxv是满足 a[i] > b[k] 的 f[i - 1][k] + 1 的前缀最大值。
因此可以直接将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环。
而每次用到的 状态 都是第 i - 1 个阶段的
因此我们可以用一个变量，存储上一个阶段的能够接在 a[i] 前面的最大的状态值
'''以上，最长公共上升子序列文章来源：https://www.toymoban.com/news/detail-407112.html
祝好~文章来源地址https://www.toymoban.com/news/detail-407112.html
到了这里，关于最长公共上升子序列（LCIS）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
