长度为k的增加字符串的数量 [英] number of increasing strings of length k

问题描述

我很难发现如何在 n 号码中找到长度为 k 的日益增加的序列的数量。我知道它已经使用了 LIS 问题，我必须以某种方式修改它，但现在得到了如何。它的复杂性是 O（k * n ^ 2） DP解决方案。请提供一点点解释一下。

I am finding it hard that how to find the number of increasing sequences of length k in n numbers. I know it has use of LIS problem and I have to modify it somehow, but now getting how. It's complexity is O(k*n^2) DP solution. Please give hint and explain me a little bit.

推荐答案

也许稍晚，但这可能会有帮助：

Maybe a little late but this can be helpful:

有两种算法（据我所知），用于解决这个问题。我将描述具有O（n ^ 2 * k）复杂度的那个。

There are two algorithms (as far as I know) that are used to solve this problem. Im going to describe the one with O(n^2*k) complexity.

此算法使用DP解决方案;这是LIS问题的一个扭曲。在LIS问题中，您使用1D数组来存储LIS的长度，直到元素i，这意味着dp [i] = LIS的长度，直到元素i。这将导致一个算法，如：

This algoritm uses a DP solution; it's a twist of the LIS problem. In the LIS problem, you use a 1D array to store the length of the LIS until element i, that means dp[i] = length of the LIS until element i. This would lead to an algorithm like:

/* let dp[] be the array that stores the length of the LIS found so far.
 v[] is the array of the values

 LIS(0) = 1
 LIS(i) = 1 + max(LIS(j) where j in [1..i-1] and v[j] < v[i]);
*/

dp[0] = 1;
for (int i=1 ; i<n ; i++)
    for (int j=0 ; j<i ; j++) if (v[j] < v[i])
        dp[i] = 1 + max(dp[i], dp[j]);

然后，我们可以将其带到另一个级别，然后获取长度为k的增加子序列的数量。该算法使用相同的原理。

Then, we can take this to another level, and then get the amount of increasing subsequences of length k. The algorithm uses the same principle.

/*
  dp[i][k] -> Stores the number of subsequences of length k until character i
  v[] -> The values
  n -> The size of the array
  K -> the number of IS we are looking for

  The idea is to increment the value of this quantity, by the amount of the sequences
  found in the same character and the previous length. This will be better ilustrated int 
  the algorithm
*/

int totalIS = 0;
for (int i=0 ; i<n ; i++) {
    dp[i][1] = 1; // Number of subsequences of length 1 until element i
    for (int k=2 ; k<=K ; k++) { // For all the possible sizes of subsequence until k
        for (int j=0 ; j<i ; j++) if (v[j] < v[i]) {
            dp[i][k] += dp[j][k-1]; // Increment the actual amount by dp[j][k-1], which means
                                // the amound of IS of length k-1 until char j
        }
    }
    totalIS += dp[i][K]; // This can also be done in a separated cycle.
}

// The total amount of IS of length K is in totalIS

如果您有任何疑问，只需让我知道。

If you have any doubts, just let me know.

这篇关于长度为k的增加字符串的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！