为多个序列最长公共子

本文介绍了为多个序列最长公共子的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我已经做了一堆的研究寻找最长为M = 2的序列，但我试图找出如何做到这一点的M> = 2的序列。我被指定N和M：M序列，具有N个独特的元素。 N是集合{1 - N}。我曾经想过，动态规划方法，但我仍然困惑，如何真正将它。I have done a bunch of research for finding the longest for M=2 sequences, but I am trying to figure out how to do it for M>=2 sequences. I am being given N and M: M sequences, with N unique elements. N is the set of {1 - N}. I have thought about the dynamic programming approach, but I am still confused as to how to actually incorporate it. 例输入 5 3 5 3 4 1 2 2 5 4 3 1 5 2 3 1 4 Example input5 35 3 4 1 22 5 4 3 15 2 3 1 4 这里的最大序列可被看作是 5 3 1 The max sequence here can be seen to be5 3 1 预计产量 长度= 3 Expected outputLength = 3推荐答案一个简单的想法。对于每个编号我的 1 和 N ，计算最长的子序列，其中最后一个数字是我。 （我们称之为 A [1] ）For each number i between 1 and N, calculate the longest subsequence where the last number is i. (Let's call it a[i])要做到这一点，我们将遍历号我从开始的第一个序列结束。如果 A [1]＆GT; 1 ，然后还有一些Ĵ，使得每个序列中谈到之前我。现在，我们可以只检查Ĵ的所有可能值及（如previous条件成立）做 A [1] = MAX（A [1 ]，一个[J] + 1）。To do that, we'll iterate over numbers i in the first sequence from start to end. If a[i] > 1, then there's number j such that in each sequence it comes before i.Now we can just check all possible values of j and (if previous condition holds) do a[i] = max(a[i], a[j] + 1).随着最后一位​​，因为Ĵ来之前我在第一个序列，这意味着一[J] 已计算。As the last bit, because j comes before i in first sequence, it means a[j] is already calculated.for each i in first_sequence // for the OP's example, 'i' would take values [5, 3, 4, 1, 2], in this order a[i] = 1; for each j in 1..N if j is before i in each sequence a[i] = max(a[i], a[j] + 1) end endend这是 O（N ^ 2 * M），如果计算位置矩阵事先。It's O(N^2*M), if you calculate matrix of positions beforehand. 这篇关于为多个序列最长公共子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！