最长公共上升子序列(LCIS)的平方算法_最长公共上升子序列 - CSDN文库

需积分: 49 169 浏览量更新于2023-06-21 评论收藏 36KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

最长公共上升子序列（LCIS）的 O(n^2)算

法

预备知识：动态规划的基本思想，LCS，LIS。

问题：字符串 a，字符串 b，求 a 和 b 的 LCIS（最长公共上升子序列）。

首先我们可以看到，这个问题具有相当多的重叠子问题。于是我们想到用 DP 搞。DP 的首

要任务是什么？定义状态。

1 定义状态 F[i][j]表示以 a 串的前 i 个字符 b 串的前 j 个字符

且以 b[j]为结尾构成的 LCIS 的长度。

为什么是这个而不是其他的状态定义？最重要的原因是我只会这个，还有一个原因是我知

道这个定义能搞到平方的算法。而我这只会这个的原因是，这个状态定义实在是太好用了

这一点我后面再说。

我们来考察一下这个这个状态。思考这个状态能转移到哪些状态似乎有些棘手，如果把思

路逆转一下，考察这个状态的最优值依赖于哪些状态，就容易许多了。这个状态依赖于哪

些状态呢？

首先，在 a[i]!=b[j] 的时候有 F[i][j]=F[i-1][j] 。为什么呢？因为 F[i][j] 是以 b[j]为结尾的

LCIS，如果 F[i][j]>0 那么就说明 a[1]..a[i]中必然有一个字符 a[k]等于 b[j]（如果 F[i][j]等于

0 呢？那赋值与否都没有什么影响了）。因为 a[k]!=a[i]，那么 a[i]对 F[i][j]没有贡献，于是

我们不考虑它照样能得出 F[i][j]的最优值。所以在 a[i]!=b[j]的情况下必然有 F[i][j]=F[i-1]

[j]。这一点参考 LCS 的处理方法。

那如果 a[i]==b[j]呢？首先，这个等于起码保证了长度为 1 的 LCIS。然后我们还需要去找一

个最长的且能让 b[j]接在其末尾的 LCIS。之前最长的 LCIS 在哪呢？首先我们要去找的 F 数

组的第一维必然是 i-1。因为 i 已经拿去和 b[j]配对去了，不能用了。并且也不能是 i-2，因

为 i-1 必然比 i-2 更优。第二维呢？那就需要枚举 b[1]..b[j-1]了，因为你不知道这里面哪个

最长且哪个小于 b[j]。这里还有一个问题，可不可能不配对呢？也就是在 a[i]==b[j]的情况

下，需不需要考虑 F[i][j]=F[i-1][j]的决策呢？答案是不需要。因为如果 b[j]不和 a[i]配对，

那就是和之前的 a[1]..a[j-1]配对（假设 F[i-1][j]>0，等于 0 不考虑），这样必然没有和 a[i]

配对优越。（为什么必然呢？因为 b[j]和 a[i]配对之后的转移是 max(F[i-1][k])+1，而和之前

的 i`配对则是 max(F[i`-1][k])+1。显然有 F[i][j]>F[i`][j],i`>i）

于是我们得出了状态转移方程：

a[i]!=b[j]: 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]

不难看到，这是一个时间复杂度为 O(n^3)的 DP，离平方还有一段距离。

但是，这个算法最关键的是，如果按照一个合理的递推顺序，max(F[i-1][k])的值我们可以

在之前访问 F[i][k]的时候通过维护更新一个 max 变量得到。怎么得到呢？首先递推的顺序

必须是状态的第一维在外层循环，第二维在内层循环。也就是算好了 F[1][len(b)]再去算

F[2][1]。

如果按照这个递推顺序我们可以在每次外层循环的开始加上令一个 max 变量为 0，然后开

始内层循环。当 a[i]>b[j]的时候令 max=F[i-1][j]。如果循环到了 a[i]==b[j]的时候，则令 F[i]

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论0

dr5459

粉丝: 52
资源: 1

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈