长度为k的增加子序列的数目(Number of Increasing Subsequences of

我想了解，让我在时间为O增加数组长度K的子序列的数算法（Nķ的log（n））。 我知道如何使用O（K * N ^ 2）算法来解决这个同样的问题。 我已经看过了，发现这个解决方案采用BIT（树状数组）和DP。 我还发现一些代码，但我一直无法理解它。

这里有一些链接我去过那是有帮助的。

在这里，在SO
TopCoder公司论坛
随机网页

我真的很感激，如果一些能帮助我理解这个算法。

Answer 1:

我从我的复制算法在这里 ，在这里它的逻辑解释：

dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time) 
         have a certain length

for i = 1 to n do   dp[i, 1] = 1

for p = 2 to k do // for each length this time   num = {0}

  for i = 2 to n do
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element
    // have length p - 1
    num[ array[i - 1] ] += dp[i - 1, p - 1] *1*   

    // append the current element to all those smaller than it
    // that end an increasing subsequence of length p - 1,
    // creating an increasing subsequence of length p
    for j = 1 to array[i] - 1 do *2*       
      dp[i, p] += num[j]

您可以优化*1*和*2*用线段树或二进制索引树。 这些将被用于有效地处理以下操作num数组：

• 给定(x, v)添加v到num[x]相关*1* ）;
• 鉴于x ，找到和num[1] + num[2] + ... + num[x]相关*2* ）。

这些是两个数据结构的琐碎问题。

注意：这将有复杂性O(n*k*log S)其中S就在你的数组中的值的上限。 这可能是也可能不是足够好。 为了使O(n*k*log n) ，你需要你的数组的值正常化运行上述算法之前。 正规化装置转换所有的数组值的入值低于或等于n 。 所以这：

5235 223 1000 40 40

变为：

4 2 3 1 1

这可以用一个排序（保留原有索引）来完成。

文章来源: Number of Increasing Subsequences of length k