问题引入
给定两个序列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