所有增加的子序列给出序列号？ [英] Number of all increasing subsequences in given sequence?

问题描述

您可能听说过寻找最长递增子的众所周知的问题。最优算法为O（n *日志（N））的复杂性。

You may have heard about the well-known problem of finding the longest increasing subsequence. The optimal algorithm has O(n*log(n)) complexity.

我在想找到问题的所有的增加子序列给出的顺序进行。我发现了一个问题，即我们必须找到了一些解决办法的长度K ，其中有O（N * K *的log（n））的复杂性（其中， N 的是一个长的序列）增加序列。

I was thinking about problem of finding all increasing subsequences in given sequence. I have found solution for a problem where we need to find a number of increasing subsequences of length k, which has O(n*k*log(n)) complexity (where n is a length of a sequence).

当然，这种算法可用于我的问题，但解决方案具有O（N * K *的log（n）* N）=为O（n ^ 2 * K *的log（n））的复杂性，我想。我认为，必须有一个更好的（我的意思是 - 更快）的解决方案，但我不知道这样还没有

Of course, this algorithm can be used for my problem, but then solution has O(n*k*log(n)*n) = O(n^2*k*log(n)) complexity, I suppose. I think, that there must be a better (I mean - faster) solution, but I don't know such yet.

如果你知道如何解决找出所有增加的子序列给出序列中的问题，优化的时间/复杂性（在这种情况下，最佳=比为O（n ^ 2 * K *日志（ N））），请让我知道。

If you know how to solve the problem of finding all increasing subsequences in given sequence in optimal time/complexity (in this case, optimal = better than O(n^2*k*log(n))), please let me know about that.

在底：这个问题不是一门功课。有提到我的演讲时间最长递增子的问题，我已经开始思考所有的子序列增加给定顺序的总体思路。

In the end: this problem is not a homework. There was mentioned on my lecture a problem of the longest increasing subsequence and I have started thinking about general idea of all increasing subsequences in given sequence.

推荐答案

我不知道这是否是最佳 - 可能不是，但这里的一个DP的解决方案为O（n ^ 2）。

I don't know if this is optimal - probably not, but here's a DP solution in O(n^2).

让 DP [I] =增加个子跟我一样的最后一个元素的数量

for i = 1 to n do
    dp[i] = 1
    for j = 1 to i - 1 do
        if input[j] < input[i] then
            dp[i] = dp[i] + dp[j] // we can just append input[i] to every subsequence ending with j

然后，它的所有总结中的条目 DP

这篇关于所有增加的子序列给出序列号？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！