number of increasing strings of length k

Question

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.

Answer 1

Maybe a little late but this can be helpful:

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.

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]);

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.