dynamic - 长度为 k 的递增字符串的数量

Question

我发现如何在n 个数字中找到长度为k的递增序列的数量很难。我知道它使用了LIS问题，我必须以某种方式对其进行修改，但现在知道了。它的复杂性是DP解决方案。请给出提示并稍微解释一下。O(k*n^2)

Answer 1

也许有点晚了，但这可能会有所帮助：

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

该算法使用 DP 解决方案；这是 LIS 问题的一个转折点。在 LIS 问题中，您使用一维数组来存储 LIS 直到元素 i 的长度，这意味着 dp[i] = LIS 直到元素 i 的长度。这将导致如下算法：

/* 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 的递增子序列的数量。该算法使用相同的原理。

/*
  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

如果您有任何疑问，请告诉我。