问题引入

给定两个序列A,B 求出其最长公共上升子序列

分析

本题是LIS,LCS问题的结合$\require{enclose}\enclose{updiagonalstrike}{一看就是一道水题}$ 窝萌举个栗子

$A_{1-4} = 2,2,1,3$

$B_{1-4} = 2,1,2,3$

窝萌可以设$A_0 = B_0 = -\infty$

为什么呢(窝萌后面就知道了)

状态的定义：$F_{ij}$ 表示 a以下标i结尾，b以下标j结尾，最长上升公共子序列的长度

如何得到状态转移方程呢

经过手算

$F_{00} = 0$ $F_{01} = 0$ $F_{02} = 0$ $F_{03} = 0$ $F_{04} = 0$

$F_{10} = 0$ $\color{red}{F_{11} = 1}$ $F_{12} = 1$ $F_{13} = 1$ $F_{14} = 1$

$F_{20} = 0$ $F_{21} = 1$ $F_{22} = 1$ $F_{23} = 1$ $F_{24} = 1$

$F_{30} = 0$ $F_{31} = 1$ $F_{32} = 1$ $F_{33} = 1$ $F_{34} = 1$

$F_{40} = 0$ $F_{41} = 1$ $F_{42} = 1$ $F_{43} = 1$ $\color{red}{F_{44} = 2}$

观察红色部分

窝萌可以发现一个规律，$F_{ij}$ 增加 的一个条件是 $A_i = B_j$ , 否则就继承上一个状态

窝萌可以得到半个状态转移方程

if($A_i == B_j$) $F_{ij} = ...... $

else $F_{ij} = F_{i-1j}$

窝萌再去考虑另外一半方程

结合最长上升子序列的状态转移方程$F_i=max\{F_{j} + 1\}(0 \leq j < i \mid A_j < A_i)$

窝萌尝试推导一下最长公共上升子序列问题的状态转移方程

$F_{ij}=max\{F_{i-1k} + 1\}(0 \leq k < j \mid B_k < B_i)$

因为$A_i$ 要和 $B_j$ 配对 所以是$F_{i-1k}$

又因为窝萌把$A_0$ $B_0$ 设为了$-\infty$

所以当$A_i == B_j$ 时，能保证$F_{ij}$ 至少为1 （想一想，为什么）

参考最长上升子序列,窝萌的目标是找到$F_{ij}$中最大的那个

最终算法复杂度为O($n^3$)

本题还有一种优化方法，但对这个问题的完整讨论超过了本博客的范围,请读者朋友们自行上网上搜寻资料

到这里，本弱鸡第一篇博客就写完了

OrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOrzstOstOrzstOrzstOrzstOrzstOrzstO