本文介绍了所有增加的子序列给出序列号?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

您可能听说过寻找最长递增子的众所周知的问题。最优算法为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

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

08-21 03:39