长度为k的增加子序列的数量

Question

我试图理解算法,它给出了时间O(n k log(n))中数组中长度K的增加子序列的数量.我知道如何使用O(k*n ^ 2)算法解决同样的问题.我查了一下,发现这个解决方案使用了BIT(Fenwick Tree)和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

这可以通过排序(保留原始索引)来完成.