algorithm - 给定序列中所有递增子序列的数量？

Question

您可能听说过寻找 longest increasing subsequence 的著名问题。 .最优算法具有O(n*log(n))复杂度。

我正在考虑在给定序列中找到所有递增子序列的问题。我找到了解决我们需要的问题的方法 find a number of increasing subsequences of length k ，具有 O(n*k*log(n)) 复杂度(其中 n 是序列的长度)。

当然，这个算法可以用于我的问题，但是解决方案有O(n*k*log(n)*n) = O(n^2*k*log(n)) 复杂性，我想。我认为，一定有更好(我的意思是更快)的解决方案，但我还不知道。

如果您知道如何在最优时间/复杂度内解决在给定序列中找到所有递增子序列的问题(在这种情况下，最优=优于O(n^2*k *log(n)))，请告诉我。

最后:这道题不是作业。在我的演讲中提到了最长递增子序列的问题，我开始思考给定序列中所有递增子序列的一般概念。

Answer 1

我不知道这是否是最优的 - 可能不是，但这是 O(n^2) 中的 DP 解决方案。

设 dp[i] = 以 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

中的所有条目求和了