多序列的最长公共子序列

Question

我已经做了一堆研究,找到M = 2序列的最长时间,但我想弄清楚如何为M≥2序列做到这一点

我被赋予N和M:M序列,具有N个独特元素.N是{1 - N}的集合.我已经考虑过动态编程方法,但我仍然对如何实际合并它感到困惑.

示例输入

5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

这里的最大序列可以看出来

5 3 1

预期产出

Length = 3

Answer 1

一个简单的想法。

对于和i之间的每个数字，计算最后一个数字为 的最长子序列。（我们就这样称呼它吧）1Nia[i]

为此，我们将i从头到尾迭代第一个序列中的数字。如果a[i] > 1，则有一个数字j在每个序列中都位于 之前i。
现在我们可以检查jand 的所有可能值（如果前面的条件成立） do a[i] = max(a[i], a[j] + 1)。

作为最后一位，因为在第一个序列j之前，这意味着已经计算过了。ia[j]

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
    end
end

O(N^2*M)如果你事先计算位置矩阵，那就是。