DoorKickers的博客

博客

最长公共上升子序列

2019-08-12 16:39:15 By DoorKickers

问题引入

给定两个序列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

评论

[+16]
zlt txdy!
  • 2019-08-12 16:57:14
  • Reply
@mike
  • 2019-08-12 19:50:16
  • Reply
orz zlt tsdy!!!!!!
  • 2019-08-18 18:33:45
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。